合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
我们熟悉的是两个链表之间的合并，这道题的难点在于k值是不固定的，并不知道要合并多少链表。一种很常见的想法就是使用分治法，因为合并两个有序链表是合并k个有序链表的子问题。
分治法一
多次进行两个链表之间的合并，将k个有序链表转化为(k+1)/2个有序链表。例如有6个链表时，想要合并为3个链表，则链表0与链表3合并得到新的链表0，链表1与链表4合并得到新的链表1，链表2与链表5合并得到新的链表2。最终所有链表结点都合并到了链表0，即为所求结果。
举例说明该过程：
[[1,4,5],[1,3,4],[2,6]]->[[1,2,4,5,6],[1,3,4]]->[[1,1,2,3,4,4,5,6]]
ListNode*mergeTwoLists(ListNode*l1,ListNode*l2){
ListNode*dummy=new ListNode(),*cur=dummy;
while(l1&&l2){
if(l1->val<l2->val){
cur->next=l1;
l1=l1->next;
}
else{
cur->next=l2;
l2=l2->next;
}
cur=cur->next;
}
if(l1) cur->next=l1;
if(l2) cur->next=l2;
return dummy->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n=lists.size();
//n=0返回空，n=1返回lists[0]
if(n==0) return NULL;
while(n>1){
//k为合并的步长
int k=(n+1)/2;
//如果n为奇数则正中间链表不参与合并
for(int i=0;i<n/2;++i){
//将lists[i]和lists[i+k]合并到lists[i]
lists[i]=mergeTwoLists(lists[i],lists[i+k]);
}
//将n个链表经过两两合并之后转为(n+1)/2个链表
n=k;
}
//n=1退出循环，此时所有链表都合并进了lists[0]
return lists[0];
}
分治法二
类似归并排序
ListNode*mergeTwoLists(ListNode*l1,ListNode*l2){
ListNode*dummy=new ListNode(),*cur=dummy;
while(l1&&l2){
if(l1->val<l2->val){
cur->next=l1;
l1=l1->next;
}
else{
cur->next=l2;
l2=l2->next;
}
cur=cur->next;
}
if(l1) cur->next=l1;
if(l2) cur->next=l2;
return dummy->next;
}
ListNode*helper(vector<ListNode*>&lists,int left,int right){
if(left==right) return lists[left];
int mid=(left+right)/2;
ListNode*l1=helper(lists,left,mid);
ListNode*l2=helper(lists,mid+1,right);
//当前递归层的返回值
return mergeTwoLists(l1,l2);
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n=lists.size();
if(n==0) return NULL;
return helper(lists,0,n-1);
}
最小堆
首先将k个链表的首元素添加到最小堆，取出最小元素加入到结果链表中。再将所加元素的下一个元素加入到最小堆(此时的最小元素要么还在最小堆中，要么是之前所加元素的下一个元素)，取出最小元素加入到结果链表中。以此类推，直到堆中没有元素为止。
public ListNode mergeKLists(ListNode[] lists) {
int n=lists.length;
PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>(new Comparator<ListNode>(){
public int compare(ListNode l1,ListNode l2){
return l1.val-l2.val;
}
});
ListNode dummy=new ListNode(-1);
ListNode cur=dummy;
for(int i=0;i<n;++i) {
if(lists[i]!=null){
pq.add(lists[i]);
lists[i]=lists[i].next;
}
}
while(!pq.isEmpty()){
cur.next=pq.poll();
cur=cur.next;
//将取出元素的下一个元素加入堆中
if(cur.next!=null) pq.add(cur.next);
}
return dummy.next;
}
计数排序
依次遍历所有链表，记录所有元素中的最小值和最大值，那么每个元素值必定在它们两者之间。同时记录所有元素出现的次数。然后就可以从最小值遍历到最大值，根据其出现的次数建立相应个数的结点。
public ListNode mergeKLists(ListNode[] lists) {
int n=lists.length;
ListNode dummy=new ListNode(-1),cur=dummy;
HashMap<Integer,Integer> hashmap=new HashMap<>();
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
for(int i=0;i<n;++i){
while(lists[i]!=null){
if(hashmap.containsKey(lists[i].val))
hashmap.put(lists[i].val,hashmap.get(lists[i].val)+1);
else hashmap.put(lists[i].val,1);
if(lists[i].val<min) min=lists[i].val;
if(lists[i].val>max) max=lists[i].val;
lists[i]=lists[i].next;
}
}
for(int i=min;i<=max;++i){
if(!hashmap.containsKey(i)) continue;
for(int j=0;j<hashmap.get(i);++j){
cur.next=new ListNode(i);
cur=cur.next;
}
}
return dummy.next;
}
leetcode原题：https://leetcode-cn.com/problems/merge-k-sorted-lists