Brief solution using priority_queue


  • 0
    X
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            using Pair = pair<int, ListNode*>;
            priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
            for (auto lst : lists)
                if (lst) pq.push({ lst->val, lst });
    
            ListNode dummy(0), *pre = &dummy;
            while (!pq.empty()) {
                auto pair = pq.top(); pq.pop();
                pre->next = pair.second;
                pre = pre->next;
                auto next = pre->next;
                if (next) pq.push({ next->val, next });
            }
    
            return dummy.next;
        }
    };
    

Log in to reply
 

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