C++: Merge k Sorted Lists

Thought Process

The idea lies in efficiently merging multiple sorted lists while maintaining optimal performance. We use a min-heap to always retrieve the smallest node available. First, we push the head nodes of all lists into the heap. Then, we repeatedly extract the smallest node, add it to our merged list, and push its next node into the heap if it exists. 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        typedef pair<int,ListNode*> pp;

        // Created a minHeap so that smallest node will be at top
        priority_queue<pp,vector<pp>,greater<pp>> minHeap; 

        // Push head of all the lists into the minHeap
        for(int i=0;i<lists.size();i++){

            ListNode *nod = lists[i];
            if(nod!=nullptr)
                minHeap.push({nod->val,nod});
        }

        ListNode *dummy = new ListNode();
        ListNode *tmp = dummy;

        // Process a node by node starting from the smallest node. 
        while(!minHeap.empty()){

            ListNode *curr = minHeap.top().second;
            if(curr->next!=nullptr)
                minHeap.push({curr->next->val,curr->next});
                
            tmp->next = curr;
            tmp = curr;
            minHeap.pop();
        }
        return dummy->next;
    }
};

Code Complexity

Time Complexity: O(n log k)

Each of the 'n' nodes is processed once, with heap operations taking O(log k) time for 'k' lists.

Space Complexity: O(k)

The heap stores at most 'k' nodes at any time, where 'k' is the number of lists.

Code copied!