题目：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
参考@【王尼玛】的解题思路
一、小根堆
如图：4个链表中的最小值，一定来自黄色的部分，黄色的部分就是一个小根堆。
这个堆的元素个数是lists中链表的个数，初始时只是将每个链表的头结点放入堆中，建立完初始的堆后，就不断的从堆中获取节点，如果获取到的节点不为空，即还有下一个节点，那么就将下一个节点放到堆中。
代码：
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * int val;
5 * ListNode next;
6 * ListNode() {}
7 * ListNode(int val) { this.val = val; }
8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11 class Solution {
12 public ListNode mergeKLists(ListNode[] lists) {
13 if(lists == null || lists.length == 0) return null;
14 PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>(){
15 public int compare(ListNode l1, ListNode l2){
16 //升序
17 return l1.val - l2.val;
18 }
19 });
20 ListNode dummy = new ListNode(0);
21 ListNode cur = dummy;
22 //把每个链表的头结点放进队列中
23 for(ListNode node: lists){
24 if(node != null){
25 queue.add(node);
26 }
27 }
28 while(!queue.isEmpty()){
29 cur.next = queue.poll();
30 cur = cur.next;
31 //将当前结点的下一个结点也放入队列中
32 if(cur.next != null){
33 queue.add(cur.next);
34 }
35 }
36 return dummy.next;
37 }
38 }
二、分治和合并
先将整个链表在中间进行拆分成两部分，然后再对这两部分继续拆分，直到拆分成最小单元（只有一个链表）时，再进行两两进行合并，合并后以当前合并后的链表为新的链表再与其他的链表进行合并。看图更容易理解
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
return mergeTwolists(lists, 0, lists.length - 1);
}
//分治
private ListNode mergeTwolists(ListNode[] lists, int start, int end){
if(start == end){
return lists[start];
}
int mid = start + (end - start) / 2;
ListNode l1 = mergeTwolists(lists, start, mid);
ListNode l2 = mergeTwolists(lists, mid+1, end);
return merge(l1, l2);
}
//合并
private ListNode merge(ListNode a, ListNode b){
if(a == null || b == null){
return (a == null) ? b : a;
}
if(a.val < b.val){
a.next = merge(a.next, b);
return a;
}else{
b.next = merge(a, b.next);
return b;
}
}
}
