No.21, Merge Two Sorted Lists
No.23, Merge k Sorted Lists
第一个题是合并两个已经排序的链表，第二个题是合并k个已经排序的链表。
第一个题是第二个题的基础，代码只贴第二题的，其中包含了第一题的方法。
第一个题比较简单，每次取链表中未合并的部分中两个最小值比较即可，将小的放入结果链表。如果其中一个链表已经合并完成（即剩余的为空），则把另一个链表剩余的部分直接放在结果链表的最后。最坏情况下要比较m+n-1次（两个链表的长度为m，n）。
第二题，有两种思路，一种是两两合并，一种是K个链表一起比较。
第一种思路，也有不同的实现方案，一种是从第一个开始，顺序向下合并；另一种是按照二分的方法合并，例如一共有4个链表，lists[0]和lists[2]合并，lists[1]和lists[3]合并，再将这两个合并的结果进行合并，得到最终的结果。这两种方案复杂度是不一样的，假设所有链表一共有n个数字。第一种方法要合并k-1次，最坏情况每次合并都要比较n-k次（第一个链表长度特别长，其他链表不为空且数字比第一个链表的都要大），那么复杂度为O(nk)。第二个方法，一共要比较logk轮，n个数字在每一轮中都会参与合并1次，这里可以想象为一个二叉树，每一层都包含了n个数字一次，高度为logk，那么这里复杂度为O(nlogk)。第一种方法提交会超时，第二种AC。
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode result; if(l1==null) return l2; if(l2==null) return l1; if(l1.val<=l2.val){ result=new ListNode(l1.val); l1=l1.next; } else{ result=new ListNode(l2.val); l2=l2.next; } ListNode p=result; while(l1!=null||l2!=null){ if(l1==null||l2!=null&&l1.val>l2.val){ p.next=new ListNode(l2.val); l2=l2.next; } else if(l2==null||l1!=null&&l1.val<=l2.val){ p.next=new ListNode(l1.val); l1=l1.next; } p=p.next; } return result; } public ListNode mergeKLists(ListNode[] lists) { int len=lists.length; if(len==0) return null; while(len>1){ int point=(len+1)/2; for(int i=0;i<len/2;i++){ lists[i]=mergeTwoLists(lists[i],lists[i+point]); } len=point; } return lists[0]; } }
那么除了两两合并，还可以k个链表一起比较。这里需要使用最小堆或者优先级队列，原理差不多，以堆为例。首先这类带有优先级的数据结构，在插入一个新的值时，重新排序的复杂度为log(n)，n为节点数。我们每次都把k个链表中未合并部分的最小值组成最小堆，堆的节点数为k，堆的第一层就是最小值，即需要拿去合并的值，该值拿走后需要再用同一个链表的下一值补充。这样一共需要进行n次（n还是全部链表的数字数量），因此复杂度还是O(nlogk)。