给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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;}}