题目：给你多条链表，举个例子，如下三条链表：
1->2->6->7
2->4->4->5
3->7->7->9
你给我合成一个大链表，每一条链表都有序，请你合成一个总的有序的链表，结果应该是：
1->2->2->3->4->4->5->6->7->7->7->9
并返回第1个节点。
图1：
图2：
图3：
图4：
思路：
1.先把每个链表的头节点放进去，放进去后天然就排好序，根据节点的值。但是每个头节点的指针还是各自指着各自的下一个节点。
2.弹出一个节点，1被弹出，是最小的节点，就是head。1的下个节点4进去，因为是小根堆有序会自己调整，4就会插在2和5之间。
3.小根堆再弹出个节点2，2的下个节点3进去，3在顶部，小根堆里面现在是3,4,5。2放在步骤2弹出的节点1后面。
4.再将3弹出来，7进去，7在4和5后面。弹出来的3放在步骤3中2节点后面。
5.周而复始，直到小根堆中的所有元素都弹出。
代码如下：
package com.cy.class06;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Code01_MergeKSortedLists {
public static class ListNode {
public int val;
public ListNode next;
}
public static class ListNodeComparator implements Comparator<ListNode> {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
}
/**
* 为什么入参是数组，lists里面n个元素，每个元素都是一个链表，而传进来的是n个链表各自的头节点。
* 怎么估算这个方法的复杂度?
*
*/
public static ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
//先把所有的头节点添加进小根堆
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
heap.add(lists[i]);
}
}
if (heap.isEmpty()) {
return null;
}
ListNode head = heap.poll();
ListNode pre = head;
if (pre.next != null) {
heap.add(pre.next);
}
while (!heap.isEmpty()) {
ListNode cur = heap.poll();
pre.next = cur;
pre = cur;
if (cur.next != null) {
heap.add(cur.next);
}
}
return head;
}
}如何估算这个算法的复杂度？
假设一共m条链表，m条链表的总节点数假设是n，小根堆因为是出来一个进去一个，所以小根堆的大小不会超过m，有关小根堆的所有操作o(logm)的复杂度。一共n个节点出去进来，一共操作n次，复杂度为：o(N * logm)
--