# C++ code O(NlogK) in time, O(1) in space, Divide_Conquer

• ``````ListNode* mergeKLists(vector<ListNode*>& lists) {
int k = (int)lists.size();
if(k==0) return NULL;
if(k==1) return lists[0];
return doMerge(lists, 0, (int)lists.size()-1);
}

ListNode* doMerge(vector<ListNode*>& lists, int left, int right) {
if(left==right) return lists[left];
else if(left+1==right) return merge2Lists(lists[left], lists[right]);
ListNode* l1 = doMerge(lists, left, (left+right)/2);
ListNode* l2 = doMerge(lists, (left+right)/2+1, right);
return merge2Lists(l1, l2);
}

ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
if(l1==l2) return l1;
if(!l1) return l2;
if(!l2) return l1;
if(l1->val>l2->val) return merge2Lists(l2, l1);
ListNode* newl2 = new ListNode(0); newl2->next = l2;
ListNode* p1 = l1;
while (p1->next && newl2->next) {
if (p1->next->val<newl2->next->val) {
p1 = p1->next;
} else {
ListNode* temp = p1->next;
p1->next = newl2->next;
newl2->next = newl2->next->next;
p1->next->next = temp;
p1 = p1->next;
}
}
if(!p1->next) p1->next = newl2->next;
delete newl2;
return l1;
}``````

• Do you mean O(NKlogK) ? How can you do it in O(nlogK) time when there are NK nodes in total that you need to visit?

• I think the divide and conquer action it self with K nodes is O(klogk), and O(n) to merge two lists. So it will be nklogk

• Oops, I thought n stands for total nodes in all. I should have point it out. My apologies.

• I had the same idea with you! ^_^

`````` ListNode *merge2Lists(ListNode *list1, ListNode *list2)
{
if(NULL == list1) return list2;
if(NULL == list2) return list1;
ListNode res(0);
ListNode *curRes = &res, *cur1 = list1, *cur2=list2;
while(cur1 != NULL && cur2 != NULL)
{
if(cur1->val < cur2->val)
{
curRes->next = cur1;
cur1 = cur1->next;
}else
{
curRes->next = cur2;
cur2 = cur2->next;
}
curRes = curRes->next;
}
curRes->next = cur1 ? cur1 : cur2;
return res.next;
}
ListNode *mergeKLists(ListNode *list[], int size){
if(0 == size) return NULL;
if(1 == size) return list[0];
if(2 == size)
{
return merge2Lists(list[0], list[1]);
}
int mid = size>>1;
ListNode *subList1 = mergeKLists(list, mid);
ListNode *subList2 = mergeKLists(&list[mid], size - mid);
return merge2Lists(subList1, subList2);
}
ListNode *mergeKLists(vector<ListNode *> &lists) {
return mergeKLists(&lists[0], lists.size());
}``````

• the time complexity of your algorithm is o(nklogk), absolutely.
assume the average length of lists is n, there are k lists.
firstly, merge every two list need nk/2; in the next round, the length of list becomes 2n, the number of lists becomes k/2, so the complexity is still nk/2. Keep such rounds until k == 1, that would be log(k) rounds. so the total complexity is nklog(k)

• doMerge is a recursion call, which has logK depth.
Space complexity is O(logK).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.