这道题可以利用merge 2 sorted list。想到D&C， K个list可以被二分，分到最后只有2个list的情况。
画成树的话，一共有lgK个level, mergeTwoList的时间是O(n)，
所以这道题利用Divide and Conquer，和merge2list，running time应该是O(nlgK):
看见有人用priority queue和comparator做。但速度并没有提升。
下次刷的时候，研究研究那种做法。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if (lists == null || len == 0) return null;
else if (len == 1) return lists[0];
else {
ListNode[] list1 = Arrays.copyOfRange(lists, 0, len/2);
ListNode[] list2 = Arrays.copyOfRange(lists, len/2, len);
ListNode l1 = mergeKLists(list1);
ListNode l2 = mergeKLists(list2);
ListNode l3 = mergeTwoLists(l1, l2);
return l3;
}
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
