Merge K Sorted Lists Using Min Heap in DSA C++

Mental Model

We combine many sorted lists into one sorted list by always picking the smallest current element from all lists using a small helper structure.

Analogy: Imagine you have K friends each with a sorted list of candies by sweetness. You want to pick candies one by one in order of sweetness. You ask each friend for their smallest candy and pick the sweetest among those smallest candies, then ask that friend for their next candy, repeating until all candies are picked.

List1: 1 -> 4 -> 7 -> null
List2: 2 -> 5 -> 8 -> null
List3: 3 -> 6 -> 9 -> null

MinHeap: [1, 2, 3]

Merged: null

Dry Run Walkthrough

Input: lists: [1->4->7, 2->5->8, 3->6->9]

Goal: Merge all 3 sorted lists into one sorted list: 1->2->3->4->5->6->7->8->9

Step 1: Insert first nodes of all lists into min heap

MinHeap: [1, 2, 3]
Merged: null

Why: We start by knowing the smallest elements from each list to pick the smallest overall

Step 2: Extract min (1) from heap and add to merged list; insert next node (4) from list1 into heap

MinHeap: [2, 3, 4]
Merged: 1 -> null

Why: We pick the smallest element and then add the next candidate from that list

Step 3: Extract min (2) from heap and add to merged list; insert next node (5) from list2 into heap

MinHeap: [3, 4, 5]
Merged: 1 -> 2 -> null

Why: Continue picking smallest and replenishing heap with next nodes

Step 4: Extract min (3) from heap and add to merged list; insert next node (6) from list3 into heap

MinHeap: [4, 5, 6]
Merged: 1 -> 2 -> 3 -> null

Why: Keep merging by always picking the smallest current element

Step 5: Extract min (4) from heap and add to merged list; insert next node (7) from list1 into heap

MinHeap: [5, 6, 7]
Merged: 1 -> 2 -> 3 -> 4 -> null

Why: Add next smallest and continue until all lists are exhausted

Step 6: Extract min (5) from heap and add to merged list; insert next node (8) from list2 into heap

MinHeap: [6, 7, 8]
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Keep merging by replenishing heap with next nodes

Step 7: Extract min (6) from heap and add to merged list; insert next node (9) from list3 into heap

MinHeap: [7, 8, 9]
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Why: Continue until all nodes are merged

Step 8: Extract min (7) from heap and add to merged list; list1 exhausted, no insertion

MinHeap: [8, 9]
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null

Why: No more nodes in list1, just add remaining from others

Step 9: Extract min (8) from heap and add to merged list; list2 exhausted, no insertion

MinHeap: [9]
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

Why: Continue adding remaining nodes

Step 10: Extract min (9) from heap and add to merged list; list3 exhausted, heap empty

MinHeap: []
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Why: All nodes merged, heap empty, done

Result:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Comparator for min heap to compare ListNode pointers by their val
struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, Compare> minHeap;

    // Push first node of each list into min heap
    for (auto node : lists) {
        if (node != nullptr) {
            minHeap.push(node); // add smallest candidates
        }
    }

    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (!minHeap.empty()) {
        ListNode* smallest = minHeap.top();
        minHeap.pop(); // get smallest node

        tail->next = smallest; // add to merged list
        tail = tail->next;

        if (smallest->next != nullptr) {
            minHeap.push(smallest->next); // add next node from same list
        }
    }

    return dummy.next;
}

void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << " -> null" << endl;
}

int main() {
    // Create lists: [1->4->7], [2->5->8], [3->6->9]
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(7);

    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(5);
    l2->next->next = new ListNode(8);

    ListNode* l3 = new ListNode(3);
    l3->next = new ListNode(6);
    l3->next->next = new ListNode(9);

    vector<ListNode*> lists = {l1, l2, l3};

    ListNode* merged = mergeKLists(lists);
    printList(merged);

    return 0;
}

for (auto node : lists) { if (node != nullptr) { minHeap.push(node); } }

Add first node of each list to min heap to start merging

while (!minHeap.empty()) {

Repeat until all nodes are merged

ListNode* smallest = minHeap.top(); minHeap.pop();

Extract smallest node from min heap

tail->next = smallest; tail = tail->next;

Add smallest node to merged list and move tail pointer

if (smallest->next != nullptr) { minHeap.push(smallest->next); }

Add next node from the same list to min heap if exists

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Complexity Analysis

Time: O(N log K) because we process all N nodes and each insertion/extraction from min heap of size K costs O(log K)

Space: O(K) because the min heap stores at most one node from each of the K lists at a time

vs Alternative: Naive merging by repeatedly merging two lists costs O(KN) which is slower; min heap approach is more efficient for large K

Edge Cases

Empty input lists vector

Returns null immediately, no nodes to merge

DSA C++

if (node != nullptr) { minHeap.push(node); }

Some lists are empty (null)

Only non-empty lists contribute nodes; empty lists ignored

DSA C++

if (node != nullptr) { minHeap.push(node); }

All lists empty

Returns null, merged list is empty

DSA C++

while (!minHeap.empty()) { ... }

When to Use This Pattern

When you need to merge multiple sorted lists efficiently, especially when K is large, use a min heap to always pick the smallest current element from all lists.

Common Mistakes

Mistake: Not pushing the next node of the extracted node back into the min heap
Fix: After extracting the smallest node, always push its next node into the min heap if it exists

Mistake: Using a max heap or incorrect comparator causing wrong order
Fix: Use a min heap with comparator that compares nodes by their value in ascending order

Summary

Merges K sorted linked lists into one sorted list using a min heap to efficiently pick the smallest node.

Use when you have multiple sorted lists and want to merge them quickly without repeatedly merging pairs.

The key insight is to keep track of the smallest current nodes from all lists in a min heap and always pick the smallest to build the merged list.