C++ O(nklogk) Time, O(k) Space, 14 Lines, Concise and Elegant code using priority_queue


  • 3
    F
    ListNode* mergeKLists(vector<ListNode*>& heads) {
        auto comp = [](ListNode * a, ListNode * b){return a->val > b->val;};
        priority_queue<ListNode *, vector<ListNode *>, decltype(comp)> min_heap(comp);
        for (auto & head : heads)
            if (head) min_heap.push(head);
        ListNode * head = new ListNode(0), * tail = head;
        while(min_heap.size()) {
            auto cur = min_heap.top();
            min_heap.pop();
            tail->next = cur;
            tail = cur;
            if (cur->next) min_heap.push(cur->next);
            cur->next = nullptr;
        }
        return head->next;
    }

  • 0
    Q

    I got a question that what the operation of " tail->next = cur; tail = cur;" mean.Thanks a lot.


  • 0
    F

    tail is pointing to the "tail" (end) of the list I'm building. tail->next = cur is to append cur to tail (in other words, to the list). cur = tail; is to update tail to the newly appended node, because this node is now the end of the list. Hope I expressed it clearly.


  • 0
    Q

    @fentoyal I finally got it.Thank you.


  • 0
    F

    Good code. A small issue that the function is leak memory of head.


  • 0
    F

    @fei26 No. There is no memory leaking here, because we know this code is NOT called by a long-running service. If a piece of code is called only a few times before main function returns, there won't be any memory leaking. This is because CRL automatically release all resources -- even when the resource has no reference to it.


Log in to reply
 

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