A simple C++ solution (O(nklog(k)) running time and O(1) memory).


  • 0
    S
    ListNode* merge(ListNode* a, ListNode* b) {
        if (!a) return b;
        if (!b) return a;
    
        ListNode dum{42};
        ListNode *cur = &dum;
        while (a && b) {
            if (a->val <= b->val) {
                cur->next = a;
                cur = a;
                a = a->next;
            } else {
                cur->next = b;
                cur = b;
                b = b->next;
            }
        }
        if (a) cur->next = a;
        else cur->next = b;
        
        return dum.next;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
    
        while (lists.size() > 1) {
            for (int i = 0; i < lists.size() - 1; i += 2) {
                lists[i] = merge(lists[i], lists[i + 1]);
                lists[i + 1] = nullptr;
            }
            int indx = 0;
            for (auto p : lists) if (p) lists[indx++] = p;
            lists.erase(lists.begin() + indx, lists.end());
        }
    
        return *lists.begin();
    }
    

    };


Log in to reply
 

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