c++ solution with priority_queue


  • 1
    W

    Since all lists are sorted, thus the head of each list is the smallest node in the list.
    At first, put all heads of lists in a min heap, the top of heap will be the smallest node among all the lists.
    Then pop the smallest node from the heap, and add it to the merged lists. After popping the top, the next item of the top node should be pushed into the queue.
    Stop when the queue is empty, which means all the nodes have been added to the merged lists.

    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            // create a min heap
            auto cmp = [](ListNode*& lhs, ListNode*& rhs) { return lhs->val > rhs->val; };
            priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
            
            for (auto node : lists) {
                if (node)
                    pq.push(node);
            }
            
            ListNode* sentinel = new ListNode(-1);
            ListNode* last = sentinel;
            while (!pq.empty()) {
                auto node = pq.top();
                pq.pop();
                last->next = node;
                last = node;
                if (node->next)
                    pq.push(node->next);
            }
            
            return sentinel->next;
        }
    };
    

Log in to reply
 

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