Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
解题思路一：
之前我们有mergeTwoLists(ListNode l1, ListNode l2)方法，直接调用的话，需要k-1次调用，每次调用都需要产生一个ListNode[]，空间开销很大。如果采用分治的思想，对相邻的两个ListNode进行mergeTwoLists，每次将规模减少一半，直到规模变为2为止，空间开销就会小很多。JAVA实现如下：
static public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0)
return null;
if (lists.length == 1)
return lists[0];
if (lists.length == 2)
return mergeTwoLists(lists[0], lists[1]);//参考Java for LeetCode 021 Merge Two Sorted Lists
else {
ListNode[] halfLists = new ListNode[lists.length / 2];
if (lists.length % 2 == 0)
for (int i = 0; i < halfLists.length; i++)
halfLists[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
else {
for (int i = 0; i < halfLists.length; i++)
halfLists[i] = mergeTwoLists(lists[2 * i], lists[2 * i + 1]);
halfLists[0] = mergeTwoLists(halfLists[0],lists[lists.length - 1]);
}
return mergeKLists(halfLists);
}
}
解题思路二：
采用优先级队列，每次将List[]中的元素入队，然后让最小的元素出队，注意Comparator的重写，JAVA实现如下：
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> queen = new PriorityQueue<ListNode>(
0,new Comparator<ListNode>() {//提交的时候不能加初始容量（第一个参数），否则报错
public int compare(ListNode l1, ListNode l2) {
return l1.val - l2.val;
}
});
ListNode result = new ListNode(0), index = result,poll;
for (ListNode list : lists)
if (list != null)
queen.add(list);
while (!queen.isEmpty()) {
poll=queen.poll();
index.next = new ListNode(poll.val);
index = index.next;
if (poll.next != null)
queen.add(poll.next);
}
return result.next;
}