Merge K Sorted Lists Using Min Heap in DSA C#

Mental Model

We combine multiple sorted lists into one sorted list by always picking the smallest current element from all lists.

Analogy: Imagine you have K friends each reading a sorted book. You want to write down all the words in order. You ask each friend for their current word and pick the smallest one to write down, then ask that friend for their next word, repeating until all words are written.

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

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

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 add smallest element and bring 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

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 smallest 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 update heap

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: Continue merging

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: Keep smallest element at top

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 to add

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: No more nodes in list2 to add

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

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

Why: All lists exhausted, merging complete

Result:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        var comparer = Comparer<ListNode>.Create((a, b) => a.val - b.val);
        var minHeap = new SortedSet<(ListNode node, int id)>(Comparer<(ListNode, int)>.Create((a, b) => {
            int cmp = a.node.val.CompareTo(b.node.val);
            if (cmp == 0) return a.id - b.id;
            return cmp;
        }));

        // Insert first node of each list into minHeap
        for (int i = 0; i < lists.Length; i++) {
            if (lists[i] != null) {
                minHeap.Add((lists[i], i));
            }
        }

        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        while (minHeap.Count > 0) {
            var min = minHeap.Min; // get smallest node
            minHeap.Remove(min); // remove it from heap

            current.next = min.node; // add smallest node to merged list
            current = current.next;

            if (min.node.next != null) {
                minHeap.Add((min.node.next, min.id)); // add next node from same list
            }
        }

        return dummy.next;
    }

    static void PrintList(ListNode head) {
        while (head != null) {
            Console.Write(head.val);
            if (head.next != null) Console.Write(" -> ");
            head = head.next;
        }
        Console.WriteLine(" -> null");
    }

    public static void Main() {
        var lists = new ListNode[3];
        lists[0] = new ListNode(1, new ListNode(4, new ListNode(7)));
        lists[1] = new ListNode(2, new ListNode(5, new ListNode(8)));
        lists[2] = new ListNode(3, new ListNode(6, new ListNode(9)));

        var solution = new Solution();
        var merged = solution.MergeKLists(lists);
        PrintList(merged);
    }
}

for (int i = 0; i < lists.Length; i++) { if (lists[i] != null) { minHeap.Add((lists[i], i)); } }

Insert first node of each list into min heap to start merging

while (minHeap.Count > 0) { var min = minHeap.Min; minHeap.Remove(min);

Extract the smallest node from min heap to add to merged list

current.next = min.node; current = current.next;

Add extracted smallest node to merged list and move current pointer

if (min.node.next != null) { minHeap.Add((min.node.next, min.id)); }

Insert next node from the same list into 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/removal in the heap of size k costs O(log k)

Space: O(k) because the 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

All input lists are empty

Returns null as merged list is empty

DSA C#

if (lists[i] != null) { minHeap.Add((lists[i], i)); }

Some lists are empty, others have nodes

Only non-empty lists contribute nodes to merged list

DSA C#

if (lists[i] != null) { minHeap.Add((lists[i], i)); }

Lists contain duplicate values

Duplicates are merged correctly maintaining sorted order

DSA C#

Comparer<(ListNode, int)>.Create((a, b) => { int cmp = a.node.val.CompareTo(b.node.val); if (cmp == 0) return a.id - b.id; return cmp; })

When to Use This Pattern

When you need to merge multiple sorted lists or streams efficiently, use a min heap to always pick the smallest current element from all lists.

Common Mistakes

Mistake: Not handling duplicate values in the min heap causing comparison errors
Fix: Add a tie-breaker (like list index) in the comparer to avoid conflicts

Mistake: Inserting null nodes into the heap causing runtime errors
Fix: Check for null before inserting nodes into the heap

Mistake: Not updating the current pointer after adding a node to merged list
Fix: Move current pointer forward after attaching the smallest node

Summary

Merges k sorted linked lists into one sorted linked list using a min heap.

Use when you have multiple sorted lists and want to combine them efficiently.

Always pick the smallest current element from all lists using a min heap to maintain order.

Practice

1. What is the main purpose of using a min heap when merging K sorted linked lists?

easy

A. To efficiently get the smallest current element among all lists

B. To store all elements in sorted order before merging

C. To reverse the order of elements in each list

D. To count the total number of elements in all lists

Solution

1. Step 1: Understand the role of min heap in merging

   A min heap helps quickly find the smallest element among multiple sorted lists without scanning all elements.

2. Step 2: Why min heap is chosen

   It maintains the smallest element at the top, so we can pick and remove it efficiently while merging.

3. Final Answer:

   To efficiently get the smallest current element among all lists -> Option A

4. Quick Check:

   Min heap = smallest element retrieval [OK]

Hint: Min heap always gives smallest element fast [OK]

Common Mistakes:

• Thinking min heap stores all elements sorted
• Confusing min heap with max heap
• Using min heap to count elements

2. Which of the following is the correct way to initialize a min heap in C# for merging K sorted lists?

easy

A. var minHeap = new List<int>();

B. var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>();

C. var minHeap = new Queue<ListNode>();

D. var minHeap = new Stack<ListNode>();

Solution

1. Step 1: Identify data structure for min heap

   SortedSet with tuple (value, list index, node) can act as a min heap by sorting elements by value.

2. Step 2: Why other options are incorrect

   List, Queue, and Stack do not maintain sorted order automatically, so they can't serve as min heap.

3. Final Answer:

   var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>(); -> Option B

4. Quick Check:

   SortedSet = min heap structure [OK]

Hint: Use SortedSet with tuples for min heap in C# [OK]

Common Mistakes:

• Using List or Queue as min heap
• Not including value for sorting in tuple
• Confusing Stack with heap

3. What will be the output linked list after merging these 3 sorted lists using a min heap?

List 1: 1 -> 4 -> 5 -> null
List 2: 1 -> 3 -> 4 -> null
List 3: 2 -> 6 -> null

medium

A. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

B. 1 -> 3 -> 4 -> 1 -> 4 -> 5 -> 2 -> 6 -> null

C. 6 -> 5 -> 4 -> 4 -> 3 -> 2 -> 1 -> 1 -> null

D. 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

Solution

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

   Insert 1 (List1), 1 (List2), 2 (List3) into min heap.

2. Step 2: Extract min and add next nodes

   Extract 1 (List1), add 4; extract 1 (List2), add 3; extract 2 (List3), add 6; continue extracting min and adding next nodes until all lists are merged.

3. Final Answer:

   1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null -> Option D

4. Quick Check:

   Merge sorted lists = sorted combined list [OK]

Hint: Always pick smallest node from heap and add next from same list [OK]

Common Mistakes:

• Not adding next node after extracting min
• Merging lists without sorting
• Confusing order of nodes

4. Given the following code snippet for merging K sorted lists, what is the error?

var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>();
foreach (var list in lists) {
  if (list != null) minHeap.Add((list.val, 0, list));
}
while (minHeap.Count > 0) {
  var min = minHeap.Min;
  minHeap.Remove(min);
  // Add min.node to result
  if (min.node.next != null) {
    minHeap.Add((min.node.next.val, min.listIndex + 1, min.node.next));
  }
}

medium

A. Incrementing listIndex incorrectly when adding next node

B. Not checking if list is null before adding to heap

C. Using SortedSet instead of PriorityQueue

D. Not removing min element from heap

Solution

1. Step 1: Understand listIndex usage

   listIndex should identify which list the node belongs to and remain constant for that list.

2. Step 2: Identify error in incrementing listIndex

   Incrementing listIndex by 1 when adding next node is wrong; it should stay the same to track correct list.

3. Final Answer:

   Incrementing listIndex incorrectly when adding next node -> Option A

4. Quick Check:

   listIndex must not change per node [OK]

Hint: Keep listIndex fixed per list, don't increment per node [OK]

Common Mistakes:

• Changing listIndex for next nodes
• Forgetting to remove min element
• Ignoring null checks

5. You have 4 sorted linked lists with lengths 2, 3, 4, and 5 respectively. Using a min heap, what is the time complexity to merge all lists into one sorted list?

hard

A. O(N + K), where N is total nodes and K is number of lists

B. O(N K), where N is total nodes and K is number of lists

C. O(N log K), where N is total nodes and K is number of lists

D. O(K log N), where N is total nodes and K is number of lists

Solution

1. Step 1: Calculate total nodes and understand K

   Total nodes N = 2 + 3 + 4 + 5 = 14, K = 4 lists.

2. Step 2: Analyze min heap operations

   Each node is pushed and popped once from min heap of size K, so operations take O(log K) each.

3. Step 3: Combine to get total complexity

   Total time = O(N log K) because each of N nodes involves heap operations.

4. Final Answer:

   O(N log K), where N is total nodes and K is number of lists -> Option C

5. Quick Check:

   Heap operations per node = log K [OK]

Hint: Merging K lists with heap = O(N log K) time [OK]

Common Mistakes:

• Assuming O(N K) instead of O(N log K)
• Ignoring heap operation cost
• Confusing N and K roles