023. Merge k Sorted Lists

At a Glance

Topic: Linked List
Pattern: Analyze Pattern
Difficulty: Hard
LeetCode: 023

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted linked list: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

Constraints:

k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.

Approach & Solution Steps

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 JS Solution

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;
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.