合併K个排序链表
题目
合併K个排序链表，返回合併后的排序链表。请分析和描述算法复杂度。
示例：
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
Fold List 法
在函数式编程中，fold（也称为reduce，accumulate，aggregate，compress或inject）指的是一系列高阶函数，它们分析递归数据结构并通过使用给定的组合操作，重新组合递归处理结果的组成部分，建立返回值。
通常Fold由组合函数、初始值和轮入列表三部份呈现。设组合函数是f(x,y)，初始值为c，输入列表为l其中元素序列为。Fold先以初始值c为x，输入列表第一个元素为y，返回值为下一个函数计算的x，l_1为下一个函数计算的y。依此类推。
举个例子，给定如下链表：
设初始链表为空链表，
先将初始链表和第一个链表合併，
接着，合併上一步结果链表和第二个链表，
再接着重复上述步骤，合併上中步结果链表和第三个链表。
代码
package io.github.rscai.leetcode.bytedance.linktree;
public class Solution1025A {
public ListNode mergeKLists(ListNode[] lists) {
ListNode merged = null;
for (int i = 0; i < lists.length; i++) {
merged = merge(merged, lists[i]);
}
return merged;
}
private ListNode merge(ListNode firstHead, ListNode secondHead) {
ListNode mergedHead = null;
ListNode mergedTail = null;
ListNode firstCurrent = firstHead;
ListNode secondCurrent = secondHead;
while (firstCurrent != null || secondCurrent != null) {
if (firstCurrent == null) {
ListNode secondNext = secondCurrent.next;
secondCurrent.next = null;
ListNode[] headAndTail = append(mergedHead, mergedTail, secondCurrent);
mergedHead = headAndTail[0];
mergedTail = headAndTail[1];
secondCurrent = secondNext;
} else if (secondCurrent == null) {
ListNode firstNext = firstCurrent.next;
firstCurrent.next = null;
ListNode[] headAndTail = append(mergedHead, mergedTail, firstCurrent);
mergedHead = headAndTail[0];
mergedTail = headAndTail[1];
firstCurrent = firstNext;
} else if (firstCurrent.val < secondCurrent.val) {
ListNode firstNext = firstCurrent.next;
firstCurrent.next = null;
ListNode[] headAndTail = append(mergedHead, mergedTail, firstCurrent);
mergedHead = headAndTail[0];
mergedTail = headAndTail[1];
firstCurrent = firstNext;
} else {
ListNode secondNext = secondCurrent.next;
secondCurrent.next = null;
ListNode[] headAndTail = append(mergedHead, mergedTail, secondCurrent);
mergedHead = headAndTail[0];
mergedTail = headAndTail[1];
secondCurrent = secondNext;
}
}
return mergedHead;
}
private ListNode[] append(ListNode head, ListNode tail, ListNode node) {
if (tail == null) {
head = node;
tail = head;
} else {
tail.next = node;
tail = node;
}
return new ListNode[]{head, tail};
}
}
首先，设置初始值为空链表。
然后，逐一合併列表中的元素（链表）。上一步的结果作为下一步的输入之一。
最后一步结果即是最终解。
复杂度分析
时间复杂度
其对每一个链表都做了一次合併，每次合併都需遍历一次两个链表中所有的元素。所以，以n表示所有链表元素，时间复杂度为。
空间复杂度
共使用了五个变量，merged和函数merge中的mergedHead, mergedTail, firstCurrent, secondCurrent。空间复杂度为。