Divide and conquer solution


  • 2
    K

    class Solution {
    public:

    ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.empty())
        return NULL;
    return dac(lists,0,lists.size()-1);
    }
    
    private:
    ListNode* dac(vector<ListNode*>& lists,int low,int high)
    {
        int mid=(low+high)/2;
        if(low==high)
            return lists[low];
        ListNode* l1=dac(lists,low,mid);
        ListNode* l2=dac(lists,mid+1,high);
        return mergeTwoLists(l1,l2);
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        if(l1->val<l2->val)
            l1->next=mergeTwoLists(l1->next,l2);
        else
            l2->next=mergeTwoLists(l1,l2->next);
    }
    

    };


Log in to reply
 

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