023. Merge K Sorted Lists

At a Glance

Topic: linked-list
Pattern: Top-K / Heap or Divide & Conquer
Difficulty: Hard
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 23

Problem (one-liner)

Given an array of k sorted linked lists (ascending), merge them into one sorted linked list and return its head.

Recognition Cues

Multiple sorted sequences → k-way merge
Heap of size k gives O(n log k) where n is total nodes
Alternative: pairwise merge lists (divide & conquer) — same asymptotic with careful analysis

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — flatten values into an array, sort, rebuild a new list — O(n log n) time / O(n) space (loses original node reuse).
Better — repeatedly merge two lists in sequence (merge list1+list2, then +list3, …) — O(k · n) time in worst case; simple but hidden quadratic factor when lists are imbalanced.
Acceptable — divide-and-conquer pairwise merge of lists array — O(n log k) time / O(log k) recursion stack; no heap, friendlier in languages without container/heap.
Optimal — min-heap of size k holding current head per list — O(n log k) time / O(k) extra; typical interview pick for clarity and stable asymptotics on skewed inputs.

Optimal Solution

Go

import "container/heap"

type ListNode struct {
	Val  int
	Next *ListNode
}

type nodeHeap []*ListNode

func (nodes nodeHeap) Len() int           { return len(nodes) }
func (nodes nodeHeap) Less(a, b int) bool { return nodes[a].Val < nodes[b].Val }
func (nodes nodeHeap) Swap(a, b int)      { nodes[a], nodes[b] = nodes[b], nodes[a] }

func (nodes *nodeHeap) Push(value any) {
	*nodes = append(*nodes, value.(*ListNode))
}

func (nodes *nodeHeap) Pop() any {
	old := *nodes
	lastIndex := len(old) - 1
	item := old[lastIndex]
	*nodes = old[:lastIndex]
	return item
}

func mergeKLists(lists []*ListNode) *ListNode {
	minHeap := &nodeHeap{}
	heap.Init(minHeap)
	for _, head := range lists {
		if head != nil {
			heap.Push(minHeap, head)
		}
	}
	dummy := &ListNode{}
	tail := dummy
	for minHeap.Len() > 0 {
		smallest := heap.Pop(minHeap).(*ListNode)
		tail.Next = smallest
		tail = smallest
		if smallest.Next != nil {
			heap.Push(minHeap, smallest.Next)
		}
	}
	return dummy.Next
}

JavaScript

class MinHeap {
	constructor() {
		this.values = [];
	}
	push(node) {
		this.values.push(node);
		this.bubbleUp(this.values.length - 1);
	}
	pop() {
		const top = this.values[0];
		const last = this.values.pop();
		if (this.values.length > 0) {
			this.values[0] = last;
			this.bubbleDown(0);
		}
		return top;
	}
	get length() {
		return this.values.length;
	}
	bubbleUp(index) {
		while (index > 0) {
			const parentIndex = Math.floor((index - 1) / 2);
			if (this.values[parentIndex].val <= this.values[index].val) {
				break;
			}
			[this.values[parentIndex], this.values[index]] = [
				this.values[index],
				this.values[parentIndex],
			];
			index = parentIndex;
		}
	}
	bubbleDown(index) {
		const length = this.values.length;
		while (true) {
			const leftIndex = index * 2 + 1;
			const rightIndex = index * 2 + 2;
			let smallest = index;
			if (
				leftIndex < length &&
				this.values[leftIndex].val < this.values[smallest].val
			) {
				smallest = leftIndex;
			}
			if (
				rightIndex < length &&
				this.values[rightIndex].val < this.values[smallest].val
			) {
				smallest = rightIndex;
			}
			if (smallest === index) {
				break;
			}
			[this.values[index], this.values[smallest]] = [
				this.values[smallest],
				this.values[index],
			];
			index = smallest;
		}
	}
}

function mergeKLists(lists) {
	const minHeap = new MinHeap();
	for (const head of lists) {
		if (head !== null && head !== undefined) {
			minHeap.push(head);
		}
	}
	const dummy = { val: 0, next: null };
	let tail = dummy;
	while (minHeap.length > 0) {
		const smallest = minHeap.pop();
		tail.next = smallest;
		tail = smallest;
		if (smallest.next !== null) {
			minHeap.push(smallest.next);
		}
	}
	return dummy.next;
}

Walkthrough

Three lists [1,4,5], [1,3,4], [2,6]. Heap holds smallest heads 1,1,2 → pop attach → push next from that list.

Invariant: heap always contains at most one live node per non-exhausted list.

Edge Cases

Empty lists or all empty lists → null
Single non-empty list → return it
Many duplicates across lists — heap ordering stable enough by pointer identity if ties

Pitfalls

Pushing null heads into heap
Forgetting to advance with smallest.next after pop
Divide & conquer merge forgets to splice tail correctly

Variants

Merge K sorted arrays — same heap/D&C; row/col indexing instead of next pointers.
Bounded heap memory — external merge sort style multi-way merge from disk iterators.
Stable tie-breaking — if values tie, preserve input list order (heap needs (value, listIndex, node) tie-break).

Mind-Map Tags

#k-way-merge #min-heap #divide-conquer #linked-list #multilist #hard-classic