Merge K Sorted Lists Using Min Heap in DSA Go

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 reading their own 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 three 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 add the smallest element to merged list and bring in 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 smallest available node

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 update heap with next node from same list

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 in sorted order

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 heap updated with next nodes

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: Add remaining nodes until heap is empty

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 all nodes are merged

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: Heap empty means all nodes merged

Result:

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

Annotated Code

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

// ListNode defines a node in a singly linked list
// It holds an integer value and a pointer to the next node
// This is the basic building block of our lists

type ListNode struct {
	Val  int
	Next *ListNode
}

// MinHeap implements heap.Interface for []*ListNode based on node values
// This allows us to always get the smallest node efficiently

type MinHeap []*ListNode

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	// Add new node to heap
	*h = append(*h, x.(*ListNode))
}

func (h *MinHeap) Pop() interface{} {
	// Remove smallest node from heap
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

// mergeKLists merges k sorted linked lists into one sorted list
// It uses a min heap to always pick the smallest current node

func mergeKLists(lists []*ListNode) *ListNode {
	minHeap := &MinHeap{}
	heap.Init(minHeap)

	// Insert first node of each list into min heap
	for _, node := range lists {
		if node != nil {
			heap.Push(minHeap, node)
		}
	}

	dummy := &ListNode{} // Dummy head for merged list
	current := dummy

	// Extract min node and add next node from same list to heap
	for minHeap.Len() > 0 {
		minNode := heap.Pop(minHeap).(*ListNode) // smallest node
		current.Next = minNode
		current = current.Next

		if minNode.Next != nil {
			heap.Push(minHeap, minNode.Next) // add next node to heap
		}
	}

	return dummy.Next
}

// Helper to print linked list
func printList(head *ListNode) {
	for head != nil {
		fmt.Printf("%d -> ", head.Val)
		head = head.Next
	}
	fmt.Println("null")
}

func main() {
	// Create example lists: [1->4->7], [2->5->8], [3->6->9]
	l1 := &ListNode{1, &ListNode{4, &ListNode{7, nil}}}
	l2 := &ListNode{2, &ListNode{5, &ListNode{8, nil}}}
	l3 := &ListNode{3, &ListNode{6, &ListNode{9, nil}}}

	merged := mergeKLists([]*ListNode{l1, l2, l3})
	printList(merged)
}

for _, node := range lists { if node != nil { heap.Push(minHeap, node) } }

Insert first nodes of all lists into min heap to start merging

for minHeap.Len() > 0 { minNode := heap.Pop(minHeap).(*ListNode) current.Next = minNode current = current.Next if minNode.Next != nil { heap.Push(minHeap, minNode.Next) } }

Repeatedly extract smallest node and add its next node to heap to maintain sorted order

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 heap operation costs O(log k) where k is number of lists

Space: O(k) because the heap holds at most one node from each of the k lists at any time

vs Alternative: Naive approach merges lists one by one with O(kN) time, which is slower than using a min heap that merges all simultaneously

Edge Cases

Empty list of lists

Returns nil immediately, no nodes to merge

DSA Go

for _, node := range lists {
	if node != nil {
		heap.Push(minHeap, node)
	}
}

Some lists are empty

Only non-empty lists contribute nodes to heap and merged list

DSA Go

if node != nil {
	heap.Push(minHeap, node)
}

All lists empty

Returns nil merged list

DSA Go

for _, node := range lists {
	if node != nil {
		heap.Push(minHeap, node)
	}
}

When to Use This Pattern

When you need to merge multiple sorted lists efficiently, use a min heap to always pick the smallest current element from all lists to build the merged list in sorted order.

Common Mistakes

Mistake: Not pushing the next node of the extracted node back into the heap
Fix: After popping the smallest node, check if it has a next node and push that next node into the heap

Mistake: Pushing nil nodes into the heap causing runtime errors
Fix: Always check if the node is not nil before pushing into the heap

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 merge them efficiently in sorted order.

Always keep the smallest current nodes in a min heap to pick the next smallest element quickly.

Practice

1. What is the main advantage of using a min heap to merge K sorted lists?

easy

A. It uses extra memory to store all elements at once.

B. It sorts each list individually before merging.

C. It efficiently finds the smallest element among the heads of all lists.

D. It merges lists by concatenating them without sorting.

Solution

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

   A min heap keeps track of the smallest elements efficiently, allowing quick access to the smallest head among K lists.

2. Step 2: Compare other options

   Options B, C, and D do not describe the min heap's role correctly. Sorting individually or concatenating without sorting does not merge sorted lists efficiently.

3. Final Answer:

   It efficiently finds the smallest element among the heads of all lists. -> Option C

4. Quick Check:

   Min heap = efficient smallest element access [OK]

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

Common Mistakes:

• Thinking min heap sorts entire lists
• Assuming min heap stores all elements at once
• Confusing min heap with simple concatenation

2. Which Go data structure is best suited to implement a min heap for merging K sorted lists?

easy

A. map

B. linked list

C. array without heap functions

D. slice with container/heap package

Solution

1. Step 1: Identify Go's min heap implementation

   Go uses slices combined with the container/heap package to implement min heaps efficiently.

2. Step 2: Evaluate other options

   Maps and linked lists do not provide heap properties. Arrays without heap functions lack automatic heap behavior.

3. Final Answer:

   slice with container/heap package -> Option D

4. Quick Check:

   Go min heap = slice + container/heap [OK]

Hint: Use container/heap with slice for min heap in Go [OK]

Common Mistakes:

• Using map which has no order
• Using linked list which is slow for heap ops
• Ignoring container/heap package

3. What is the output of merging these 3 sorted lists using a min heap?

list1 = [1, 4, 7]
list2 = [2, 5, 8]
list3 = [3, 6, 9]

medium

A. [1, 3, 5, 7, 9, 2, 4, 6, 8]

B. [1, 2, 3, 4, 5, 6, 7, 8, 9]

C. [9, 8, 7, 6, 5, 4, 3, 2, 1]

D. [1, 4, 7, 2, 5, 8, 3, 6, 9]

Solution

1. Step 1: Understand merging with min heap

   The min heap picks the smallest head element from all lists repeatedly, producing a fully sorted merged list.

2. Step 2: Merge given lists step-by-step

   Starting with heads: 1, 2, 3; pick 1, then 2, then 3, then 4, 5, 6, 7, 8, 9 in order.

3. Final Answer:

   [1, 2, 3, 4, 5, 6, 7, 8, 9] -> Option B

4. Quick Check:

   Merge sorted lists = sorted combined list [OK]

Hint: Min heap merges by always picking smallest next element [OK]

Common Mistakes:

• Concatenating lists without sorting
• Reversing order incorrectly
• Mixing elements from different lists randomly

4. Given this Go snippet for merging K sorted lists, what is the bug?

func mergeKLists(lists [][]int) []int {
    var result []int
    h := &IntHeap{}
    heap.Init(h)
    for _, list := range lists {
        for _, val := range list {
            heap.Push(h, val)
        }
    }
    for h.Len() > 0 {
        result = append(result, heap.Pop(h).(int))
    }
    return result
}

medium

A. Pushing all elements at once loses the benefit of merging sorted lists.

B. Heap is not initialized before pushing elements.

C. Result slice is not declared properly.

D. Heap.Pop returns wrong type.

Solution

1. Step 1: Analyze the merging approach

   The code pushes all elements from all lists into the heap at once, ignoring the sorted order advantage.

2. Step 2: Understand the impact

   This approach works but is inefficient (O(N log N)) instead of O(N log K) by pushing only heads and updating heap dynamically.

3. Final Answer:

   Pushing all elements at once loses the benefit of merging sorted lists. -> Option A

4. Quick Check:

   Push all elements = inefficient merge [OK]

Hint: Push only heads, not all elements at once [OK]

Common Mistakes:

• Ignoring heap.Init call
• Misunderstanding result slice declaration
• Incorrect type assertion on Pop

5. You have K sorted linked lists of varying lengths. How would you efficiently merge them using a min heap in Go to minimize time complexity?

hard

A. Push the first node of each list into the min heap, then repeatedly pop the smallest and push its next node.

B. Push all nodes from all lists into the min heap at once, then pop all to get merged list.

C. Concatenate all lists and sort the combined list after.

D. Use a max heap instead of a min heap for merging.

Solution

1. Step 1: Use min heap with heads of each list

   Push only the first node of each list into the min heap to keep track of the smallest current element among lists.

2. Step 2: Pop smallest and push next node

   Pop the smallest node, add it to the merged list, then push the next node from that list into the heap, repeating until all nodes are processed.

3. Step 3: Time complexity advantage

   This approach runs in O(N log K) time, where N is total nodes and K is number of lists, which is efficient.

4. Final Answer:

   Push the first node of each list into the min heap, then repeatedly pop the smallest and push its next node. -> Option A

5. Quick Check:

   Push heads + pop/push next = efficient merge [OK]

Hint: Push heads only, then push next nodes dynamically [OK]

Common Mistakes:

• Pushing all nodes at once causing inefficiency
• Using max heap which gives largest element first
• Sorting concatenated list which is slower