C++ O(nk*logk) Solution ,use merge2 ,no rescursion


  • 0
    N
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())  return NULL;
        int sz=lists.size();
        if (sz==1) return lists[0];
        int j=0,end=(sz-1)<<1;
        while(j<end){
            lists.push_back(mergeTwoLists(lists[j], lists[j+1]));
            j+=2;
        }
        return lists[j];
    }

  • 0
    N

    Maybe it is hard to understand end=(sz-1)<<1
    But you can see, each merge2 reduce number of lists by 1,so we should run merge2 sz-1 times.And j increace by 2. OK?


Log in to reply
 

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