题目大意：
合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=23
解题思路分析：
听说最近有公司考到了这一题，因此决定二刷本题来压压惊。其实本题是LEETCODE 21. Merge Two Sorted Lists 解题思路分析的续集。
解法一：
前一题是合并2个链表，而本题是合并多个，核心思路没有太大差别，我们也需要两两合并，最终将多个合并成一个即可。最简单的方式即是先将前两个合并，然后再与第三个合并，再与第四个，第五个。。。直到所有合并结束。
实现代码：
public ListNode mergeKLists(ListNode[] lists) {
// 如果数组为空，返回空
if(lists.length==0) return null;
// 首个链表
ListNode node=lists[0];
for(int i=1;i<lists.length;i++){
// 将当前链表与首个链表合并，并将合并后链表赋值给node
node=merge(node, lists[i]);
}
return node;
}
// 合并2个链表
ListNode merge(ListNode l1, ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
ListNode node;
if(l1.val<=l2.val){
node=new ListNode(l1.val);
node.next = merge(l1.next, l2);
}else{
node=new ListNode(l2.val);
node.next = merge(l1, l2.next);
}
return node;
}本解法执行时间为341ms。
Runtime: 341 ms, faster than 5.06% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 43.2 MB, less than 27.33% of Java online submissions for Merge k Sorted Lists.
解法二：
解法一的代码提交后发现，执行效率并不是很高。原因在于n个链表我们需要合并n次。进而想到使用分治法， 我们两两合并，这样经过第一次合并后，链表个数减半，我们一直重复这个过程，直到最后剩余一个链表为止。 这种思路实际上也是做了n次合并，但为什么会比第一种方式更好呢？
本题优化的关键在于每次合并时遍历的节点数量。解法一中，假设有k个链表，每个链表结点数一样都为 n，第一次合并时，要遍历 2n 个结点，往后则要分别遍历 3n, 4n, … , kn 个结点。可以看到，每次进行合并时都要将之前所有的链表遍历一次，因此这个方法的时间复杂度较高 。
而解法二，第一次合并时，要进行k/2次合并，每次合并要遍历 2n 个结点；第二次合并时，要进行4/k次合并，每次合并要遍历 4n 个结点；最后一次合并过程需要遍历 kn 次结点。这样效率会大幅改善，我们更直接的看下两种解法的复杂度差别，比如我们有8个链表，每个链表有10个节点，那么：
// 解法一每次合并需要遍历的节点数量： 20+30+40+50+60+70+80=350 // 解法二每次合并需要遍历的节点数量： 20+20+20+20+40+40+80=240
如果链表个数非常庞大时，这个该改善还是非常明显的。
实现代码：
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0) return null;
// 从外向内合并首尾两个链表
int rightIndex=lists.length-1;
while(rightIndex>0){
int l=0,r=rightIndex;
while(l<r){
lists[l]=merge(lists[l],lists[r]);
l++;
r--;
}
rightIndex=r;
}
return lists[0];
}
ListNode merge(ListNode l1, ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
ListNode node;
if(l1.val<=l2.val){
node=new ListNode(l1.val);
node.next = merge(l1.next, l2);
}else{
node=new ListNode(l2.val);
node.next = merge(l1, l2.next);
}
return node;
}本题解法执行时间为3ms。
Runtime: 3 ms, faster than 86.19% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 44.4 MB, less than 23.50% of Java online submissions for Merge k Sorted Lists.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-23-merge-k-sorted-lists-解题思路分析/