题目描述
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
样例
-
样例1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6 -
样例2：
输入：lists = []
输出：[] -
样例3：
输入：lists = [[]]
输出：[]
题目评估
知识点：链表、分治算法
难度：困难
分析
如果只有两个顺序链表，把他们合并成一个顺序链表，这样的题目我们大家都会，那么现在有若干个链表，我们把他们合并成一个链表我们就会一脸懵逼。这时候采用分治算法，把这若干个链表分化成只有两个链表的问题，那么我们处理两个链表就如鱼得水了！代码如下，关键处有注释。
Java代码题解
//import java.util.Arrays;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 1) { // 如果长度等于1，直接返回那个唯一链表
return lists[0];
}
if (lists.length == 0) { // 如果长度为0，返回null
return null;
}
int mid = lists.length / 2; // 找到中点，然后分治
// 分治
ListNode leftList = mergeKLists(Arrays.copyOf(lists, mid)); // 递归中点左侧
ListNode rightList = mergeKLists(Arrays.copyOfRange(lists, mid, lists.length)); // 递归中点右侧
ListNode resListHead = new ListNode(); // 定义一个结果链表的头节点，方便后边指针后移，注意返回的时候要返回头节点的next
resListHead.next = null; // 这里给head的next赋一个null
// 定义三个指针：分别是左链表指针，右链表指针，和结果链表指针
ListNode leftPointer = leftList, rightPointer = rightList, resPointer = resListHead;
while (leftPointer != null && rightPointer != null) { // 同时遍历两个链表，比较填充给结果链表
if(leftPointer.val < rightPointer.val) { // 比较一下，谁小谁接在结果链表下边
resPointer.next = leftPointer;
leftPointer = leftPointer.next;
resPointer = resPointer.next;
} else {
resPointer.next = rightPointer;
rightPointer = rightPointer.next;
resPointer = resPointer.next;
}
}
if (leftPointer != null) { // 如果左链表剩下了，就把它全都接在结果链表下边
resPointer.next = leftPointer;
}
if (rightPointer != null) { // 如果右链表剩下了，就把它全都接在结果链表下边
resPointer.next = rightPointer;
}
return resListHead.next;
}
}
复杂度分析
递归遍历，在合并链表时是顺序的所以时间复杂度：O(n)
递归遍历使用栈空间并且有辅助的链表，空间复杂度：O(n)