023. Merge K Sorted Lists

Quick Identifier

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

Quick Sights

Time Complexity: O(n log k) from the optimal approach.
Space Complexity: O(k) from the optimal approach.
Core Mechanism: Given an array of k sorted linked lists (ascending), merge them into one sorted linked list and return its head.

Concept Explanation

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

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

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

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

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