Merge K Sorted Lists using a heap of size k.


  • 0
    H

    Problem link is this : https://leetcode.com/problems/merge-k-sorted-lists/description/

    Keep a min heap of size K initialized with first element of each of the lists. Then insert next element from the list heap's top element belong to and pop the top of the heap and add it to the final sorted list.

    struct PQE
    {
        int val;
        int iq;
        PQE(int v, int i) { val = v; iq=i;}
    };
    
    class mycompare
    {
    public:
        bool operator()(const PQE& p1, const PQE& p2) const
        {
            return p1.val >= p2.val;
        }
    };
    
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            
            ListNode* re=nullptr, *res=nullptr;
            priority_queue<PQE, vector<PQE>, mycompare> pq;
            int k = lists.size();
            
            if (k==0) return re;
            
            ListNode *n[k];
            for(int i=0;i<k;i++) {
                if (lists[i]==0) {n[i] = nullptr; continue;}
                n[i] = lists[i];
                pq.push(PQE(n[i]->val, i));
            }
            
            while(pq.size()!=0)
            {
                PQE pqe = pq.top();
                pq.pop();
                
                if (re) {re->next = new ListNode(pqe.val); re=re->next;}
                else {res = re = new ListNode(pqe.val);}
                
                n[pqe.iq] = n[pqe.iq]->next;
                if (n[pqe.iq])
                    pq.push(PQE(n[pqe.iq]->val, pqe.iq));
            }
            
            return res;
            
        }
    };
    

Log in to reply
 

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