Merge K Sorted Lists using a heap of size k.

  • 0

    Problem link is this :

    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
        bool operator()(const PQE& p1, const PQE& p2) const
            return p1.val >= p2.val;
    class Solution {
        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));
                PQE pqe =;
                if (re) {re->next = new ListNode(pqe.val); re=re->next;}
                else {res = re = new ListNode(pqe.val);}
                n[] = n[]->next;
                if (n[])
            return res;

Log in to reply

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