Merge K Sorted Lists Using Min Heap in DSA Java

Mental Model

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

Analogy: Imagine you have K friends each with a sorted list of books by height. You want to create one big sorted shelf by always asking who has the shortest book next and placing it on the shelf.

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 three 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 pick smallest element and bring next candidate from same 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: Process next smallest and add next from list1

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: Add next smallest and next from list3

Step 8: Extract min (7) from heap and add to merged list; list1 has no more nodes

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

Why: Process remaining nodes

Step 9: Extract min (8) from heap and add to merged list; list2 has no more nodes

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

Why: Continue until heap empty

Step 10: Extract min (9) from heap and add to merged list; list3 has no more nodes

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

Why: All nodes merged, heap empty

Result:

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

Annotated Code

DSA Java

import java.util.*;

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

public class MergeKSortedLists {

    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));

        // Add first node of each list to the heap
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll(); // extract min
            tail.next = smallest; // add to merged list
            tail = tail.next;
            if (smallest.next != null) {
                minHeap.offer(smallest.next); // add next node from same list
            }
        }

        return dummy.next;
    }

    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        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);

        ListNode[] lists = new ListNode[]{l1, l2, l3};

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

for (ListNode node : lists) { if (node != null) { minHeap.offer(node); } }

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

while (!minHeap.isEmpty()) {

Repeat until all nodes are merged

ListNode smallest = minHeap.poll();

Extract smallest node from heap

tail.next = smallest; tail = tail.next;

Add extracted node to merged list and move tail

if (smallest.next != null) { minHeap.offer(smallest.next); }

Add next node from same list to heap if exists

Output

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

Complexity Analysis

Time: O(N log K) because each of the N nodes is pushed and popped from a heap of size K

Space: O(K) for the heap storing one node from each list at a time

vs Alternative: Naive merging by repeated two-list merges takes O(KN) time, which is slower than using a min heap

Edge Cases

Empty input array or all lists null

Returns null immediately, no nodes to merge

DSA Java

if (node != null) { minHeap.offer(node); }

Some lists are empty (null)

Only non-null lists contribute nodes, empty lists ignored

DSA Java

if (node != null) { minHeap.offer(node); }

Lists with duplicate values

Duplicates are merged correctly maintaining sorted order

DSA Java

PriorityQueue comparator handles equal values naturally

When to Use This Pattern

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

Common Mistakes

Mistake: Not adding the next node of the extracted node back into the heap
Fix: After extracting the smallest node, always add its next node to the heap if it exists

Mistake: Using a max heap or wrong comparator causing incorrect order
Fix: Use a min heap with comparator based on node values to ensure smallest node is extracted

Summary

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

Use when you have multiple sorted lists and want an efficient combined sorted list.

The key is to always pick the smallest current node from all lists using a min heap.

Practice

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

easy

A. To efficiently get the smallest element among the heads of all lists

B. To sort each individual list before merging

C. To store all elements from all lists at once

D. To reverse the order of elements in each list

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 by always keeping the smallest element at the top.

2. Step 2: Why min heap is used here

   When merging K sorted lists, we repeatedly pick the smallest current element from all lists. The min heap efficiently supports this operation.

3. Final Answer:

   To efficiently get the smallest element among the heads of 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 sorts entire lists
• Using max heap instead of min heap
• Storing all elements at once in heap

2. Which of the following Java code snippets correctly initializes a min heap for integers?

easy

A. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.reverseOrder());

B. PriorityQueue<Integer> minHeap = new PriorityQueue<>();

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

D. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.naturalOrder().reversed());

Solution

1. Step 1: Check default behavior of PriorityQueue

   By default, Java's PriorityQueue is a min heap, so new PriorityQueue<>() creates a min heap.

2. Step 2: Analyze other options

   Options A, B, and D create max heaps using reverse order or equivalent. Only C uses the default min heap.

3. Final Answer:

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(); -> Option B

4. Quick Check:

   Default PriorityQueue = min heap [OK]

Hint: Default PriorityQueue is min heap in Java [OK]

Common Mistakes:

• Using reverseOrder() creates max heap, not min heap
• Confusing Comparator.naturalOrder() usage
• Not importing java.util.PriorityQueue

3. What will be the output of the following code snippet that merges 3 sorted lists using a min heap?

List<Integer> l1 = List.of(1, 4, 5);
List<Integer> l2 = List.of(1, 3, 4);
List<Integer> l3 = List.of(2, 6);

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

minHeap.offer(new int[]{l1.get(0), 0, 0});
minHeap.offer(new int[]{l2.get(0), 1, 0});
minHeap.offer(new int[]{l3.get(0), 2, 0});

List<Integer> result = new ArrayList<>();

while (!minHeap.isEmpty()) {
    int[] curr = minHeap.poll();
    result.add(curr[0]);
    int listIndex = curr[1];
    int elementIndex = curr[2];
    if (elementIndex + 1 < (listIndex == 0 ? l1.size() : listIndex == 1 ? l2.size() : l3.size())) {
        int nextVal = (listIndex == 0 ? l1 : listIndex == 1 ? l2 : l3).get(elementIndex + 1);
        minHeap.offer(new int[]{nextVal, listIndex, elementIndex + 1});
    }
}

System.out.println(result);

medium

A. [2, 3, 4, 5, 6]

B. [1, 2, 3, 4, 4, 5, 6]

C. [1, 1, 3, 4, 4, 5, 6]

D. [1, 1, 2, 3, 4, 4, 5, 6]

Solution

1. Step 1: Initialize min heap with first elements

   Heap starts with [1(l1), 1(l2), 2(l3)]. Poll smallest 1 from l1, add next 4 from l1. Then poll 1 from l2, add next 3 from l2, and so on.

2. Step 2: Continue polling and adding next elements

   Sequence of polled elements is 1(l1), 1(l2), 2(l3), 3(l2), 4(l1), 4(l2), 5(l1), 6(l3). This forms the merged sorted list.

3. Final Answer:

   [1, 1, 2, 3, 4, 4, 5, 6] -> Option D

4. Quick Check:

   Merged sorted list = [1,1,2,3,4,4,5,6] [OK]

Hint: Poll min, add next from same list until all merged [OK]

Common Mistakes:

• Forgetting to add next element after polling
• Mixing list indices when adding next elements
• Not handling empty lists properly

4. Identify the bug in the following code snippet that merges K sorted lists using a min heap:

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

for (int i = 0; i < lists.size(); i++) {
    if (!lists.get(i).isEmpty()) {
        minHeap.offer(new int[]{lists.get(i).get(0), i, 0});
    }
}

List<Integer> result = new ArrayList<>();

while (!minHeap.isEmpty()) {
    int[] curr = minHeap.poll();
    result.add(curr[0]);
    int listIndex = curr[1];
    int elementIndex = curr[2];
    if (elementIndex + 1 < lists.get(listIndex).size()) {
        minHeap.offer(new int[]{lists.get(listIndex).get(elementIndex + 1), listIndex, elementIndex + 1});
    }
}

medium

A. The result list is not initialized before use

B. The loop does not check for empty lists before adding

C. Comparator reverses order, creating max heap instead of min heap

D. The elementIndex is not incremented correctly when adding next element

Solution

1. Step 1: Analyze the comparator used in PriorityQueue

   The comparator (b[0] - a[0]) reverses natural order, making it a max heap, not a min heap.

2. Step 2: Effect of max heap on merging sorted lists

   Using max heap causes the largest element to be polled first, breaking the merge logic which requires smallest element first.

3. Final Answer:

   Comparator reverses order, creating max heap instead of min heap -> Option C

4. Quick Check:

   Comparator direction = min heap needed [OK]

Hint: Comparator must order ascending for min heap [OK]

Common Mistakes:

• Using (b[0] - a[0]) instead of (a[0] - b[0])
• Ignoring empty list checks
• Not incrementing elementIndex properly

5. Given K sorted linked lists, which approach best optimizes the time complexity when merging them using a min heap? A) Insert all elements from all lists into a min heap and then extract all. B) Insert only the first element of each list into the min heap and then insert next elements as you extract. C) Merge lists two at a time repeatedly without using a heap. D) Use a max heap to store all elements and then reverse the result.

hard

A. Insert first elements only, add next after extraction

B. Insert all elements at once into min heap

C. Merge lists pairwise without heap

D. Use max heap and reverse output

Solution

1. Step 1: Compare time complexities of approaches

   Inserting all elements at once (A) costs O(N log N) where N is total elements. Pairwise merging (C) costs more. Using max heap and reversing (D) is inefficient.

2. Step 2: Explain min heap incremental insertion (B)

   Inserting only first elements and adding next after extraction keeps heap size at K, leading to O(N log K) time, which is optimal.

3. Final Answer:

   Insert first elements only, add next after extraction -> Option A

4. Quick Check:

   Optimal merge = incremental min heap insertion [OK]

Hint: Keep heap size K by adding next elements after polling [OK]

Common Mistakes:

• Inserting all elements at once causing slow performance
• Using max heap incorrectly
• Ignoring heap size impact on complexity