给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = [[]]
输出：[]
思路
顺序合并
一种最朴素的方法：用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode ans = null;
for(int i=0;i<lists.length;++i){
ans = mergeList(ans,lists[i]);
}
return ans;
}
public ListNode mergeList(ListNode a,ListNode b){
if(a==null || b==null){
return a != null ? a:b;
}
ListNode head = new ListNode(0);
ListNode temp = head,temp1 = a,temp2 = b;
while(temp1!=null && temp2!=null){
if(temp1.val <temp2.val){
temp.next = temp1;
temp1 = temp1.next;
} else{
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if(temp1!=null){
temp.next = temp1;
} else{
temp.next = temp2;
}
return head.next;
}
}
分而治之
考虑优化方法一，用分治的方法进行合并。
将 k 个链表配对并将同一对中的链表合并；
第一轮合并以后， k 个链表被合并成了 k/2个链表，平均长度为 2n/k ，然后是 k/4个链表， 然后是k/8 个链表等等；
重复这一过程，直到我们得到了最终的有序链表。
return mergeList(merge(lists,l,mid),merge(lists,mid+1,r)); 这里的mid+1,r是容易错的
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists,0,lists.length -1);
}
public ListNode merge(ListNode[] lists,int l,int r){
if(l==r){
return lists[l];
}
if(l>r){
return null;
}
int mid = (l+r)>>1;
return mergeList(merge(lists,l,mid),merge(lists,mid+1,r));
}
public ListNode mergeList(ListNode a,ListNode b){
if(a==null || b==null){
return a != null ? a:b;
}
ListNode head = new ListNode(0);
ListNode temp = head,temp1 = a,temp2 = b;
while(temp1!=null && temp2!=null){
if(temp1.val <temp2.val){
temp.next = temp1;
temp1 = temp1.next;
} else{
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if(temp1!=null){
temp.next = temp1;
} else{
temp.next = temp2;
}
return head.next;
}
}