My divide and conquer C++ solution, 412ms


  • 0
    H
    class Solution {
    public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*>::iterator it;
        for(it = lists.begin(); it!=lists.end(); ){
            if(*it == NULL) it = lists.erase(it);
            else it++;
        }
        if(lists.size()<=1) return lists.size()==0?NULL:lists[0];
        ListNode* res = divide(lists, 0, lists.size()-1);
        return res;
    }
    ListNode *divide(vector<ListNode*>& lists, int a, int b){
        if(a==b) return lists[a];
        int m = (a+b)/2;
        ListNode* l1 = NULL, *l2 = NULL, *l3 = NULL, *res = NULL;
        l1 = divide(lists, a, m);
        l2 = divide(lists, m+1, b);
        if(l1->val<l2->val){
            l3 = l1; l1=l1->next;
        }
        else{
            l3 = l2; l2=l2->next;
        }
        res = l3;
        while(l1&&l2){
            if(l1->val<l2->val){
                l3->next = l1;
                l1 = l1->next;
                l3 = l3->next;
            }
            else{
                l3->next = l2;
                l2 = l2->next;
                l3 = l3->next;
            }
        }
        if(l1) l3->next = l1;
        if(l2) l3->next = l2;
        return res;
    }
    };

Log in to reply
 

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