Real divide and conquer cpp solution, O(N*logk), beat 80%, easy to understand.


  • 0
    ListNode* Divide_and_Conquer(vector<ListNode*>& lists,int i,int j){
        if(i==j)
            return lists[i];
        if(j-i==1)
            return MergeTwoLists(lists[i],lists[j]);
        return MergeTwoLists(Divide_and_Conquer(lists,i,(i+j)/2),Divide_and_Conquer(lists,(i+j)/2+1,j));
    }
    ListNode* MergeTwoLists(ListNode* l1,ListNode* l2){
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        ListNode head(0);
        ListNode *ptr=&head;
        while(l1&&l2){
            if(l1->val<l2->val){
                ptr->next=l1;
                ptr=ptr->next;
                l1=l1->next;
            }
            else{
                ptr->next=l2;
                ptr=ptr->next;
                l2=l2->next;
            }
        }
        if(!l1)
            ptr->next=l2;
        else
            ptr->next=l1;
        return head.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return nullptr;
        return Divide_and_Conquer(lists,0,lists.size()-1);
    }

  • 0

    What is the space complexity of this solution?


Log in to reply
 

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