# divide and conquer clean code beats 93%

• ``````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 + (end-start) /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

}
}
``````

• @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 divide-and-conquer takes O(n * k * log(k)):