public class Solution {
// divide and conquer
public ListNode mergeKLists(ListNode[] lists) {
return divide(lists, 0, lists.length 1);
}
private ListNode divide(ListNode[] lists, int start, int end) { // need to be lists.length() 1?
if (start > end) {
return null;
}
if (start == end) {
return lists[start];
}
int mid = start + (endstart) /2;
ListNode first = divide(lists, start,mid); // no one use mid
ListNode second = divide(lists, mid + 1, end);
return conquer(first, second);
}
private ListNode conquer(ListNode list1, ListNode list2) {
ListNode result = new ListNode(0); // dummy node > no need to manage to be
ListNode runner = result;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
runner.next = list1;
list1 = list1.next;
}else {
runner.next = list2;
list2 = list2.next;
}
runner = runner.next;
}
runner.next = list1 == null? list2 :list1;
return result.next; // delete that dummy node
}
}
divide and conquer clean code beats 93%


@keweiJ What do you think complexity of your code is?
I did almost the same and I thought the complexity was log(k) for divide, and n for conquer (actually 2n in the worst case) => overall is O(n * log(k))But this link claims that divideandconquer takes O(n * k * log(k)):
http://www.geeksforgeeks.org/mergeksortedlinkedlists/I guess I'm missing something here..