14-line easy C++ Priority Queue solution, O(Nlogk)


  • 2
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            auto lambda = [](const ListNode* p1, const ListNode* p2){return p1->val>p2->val;};
            priority_queue<ListNode*,vector<ListNode*>,decltype(lambda)> pq(lambda);
            ListNode* res = new ListNode(-1);
            ListNode* curr = res;
            for(auto it:lists)
                if(it) 
                    pq.push(it);
            while(!pq.empty()) {
                curr = (curr->next = new ListNode(pq.top()->val));
                if(pq.top()->next)
                    pq.push(pq.top()->next);
                pq.pop();
            }
            return res->next;
        }
    };
    

    Is there a way to improve the speed? Lambda or algorithm?


  • 0
    R

    it is logk*N


  • 0

    Yeah, I mistakenly represent the total number of elements as nk, but it should be N. Thank you for pointing out!


Log in to reply
 

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