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


  • 14
    J
    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;
    }

  • 0
    Y

    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?


  • 1
    Y

    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


  • 1
    J

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


  • 0
    T

    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());
        }

  • 4
    J

    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)


  • 0
    J

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


Log in to reply
 

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