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.