0
round
Given k sorted linked lists, merge them into one sorted list. The key insight is that you can reduce k lists to one in O(log k) rounds by repeatedly merging pairs — the same divide-and-conquer that powers merge sort.
You receive an array of k sorted linked lists. Return one sorted linked list containing all nodes. Example: [[1,4,5], [1,3,4], [2,6]] → [1,1,2,3,4,4,5,6]. You see this in database merge phases, external sort, and anywhere you must unify pre-sorted streams.
null. Single list → return it directly; no merging needed.Insert the head of every list into a min-heap keyed by node.val. Pop the minimum, attach it to the result, push that node's next (if any). Also O(N log k) — same asymptotic complexity but different constant factors. The heap approach is easier to extend to a streaming setting; the pairwise approach needs all lists up front and is usually simpler to implement correctly in an interview.
3 sorted lists. We will repeatedly merge pairs (divide & conquer) until one list remains.// Definition for singly-linked list.
class ListNode {
val: number;
next: ListNode | null;
constructor(val = 0, next: ListNode | null = null) {
this.val = val;
this.next = next;
}
}
// --- Approach 1: Divide & Conquer (matches the visualizer) ---
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
if (lists.length === 0) return null;
// Repeatedly halve the list of lists, merging pairs each round
let current = lists.slice();
while (current.length > 1) {
const next: Array<ListNode | null> = [];
for (let i = 0; i < current.length; i += 2) {
if (i + 1 < current.length) {
next.push(mergeTwoLists(current[i], current[i + 1]));
} else {
next.push(current[i]); // odd list — carry it over
}
}
current = next;
}
return current[0];
}
function mergeTwoLists(
a: ListNode | null,
b: ListNode | null,
): ListNode | null {
const dummy = new ListNode(0);
let tail = dummy;
while (a !== null && b !== null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next!;
}
tail.next = a ?? b;
return dummy.next;
}
// --- Approach 2: Min-Heap (O(N log k)) ---
// import { MinHeap } from 'some-heap-library'; // or implement manually
//
// function mergeKListsHeap(lists: Array<ListNode | null>): ListNode | null {
// const heap = new MinHeap<ListNode>((a, b) => a.val - b.val);
// for (const head of lists) if (head) heap.push(head);
// const dummy = new ListNode(0);
// let tail = dummy;
// while (!heap.isEmpty()) {
// const node = heap.pop()!;
// tail.next = node;
// tail = tail.next;
// if (node.next) heap.push(node.next);
// }
// return dummy.next;
// }null; a single list is already merged. These let the main loop assume ≥ 2 lists exist at the start of each iteration.current holds the working list of lists. Each iteration walks it in steps of 2, merging adjacent pairs into next. An odd-indexed tail element (i + 1 >= current.length) is carried forward without merging — it will find a partner in the next round.dummy head eliminates the special-case for the first node. tail.next = a ?? b appends whichever list still has nodes. O(m + n) time, O(1) extra space.mergeTwoLists inner loop looks like it might be O(N²) but each node is touched in exactly one merge per round, and there are log k rounds, giving O(N log k) total.| merge k sorted lists / streams | pairwise divide & conquer or min-heap |
| O(N log k) over O(N·k) | pair-merge rounds (like merge sort) |
| streaming / online merge of k sources | min-heap of size k |
| dummy head node in linked list | sentinel for clean tail attachment |
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
if (lists.length === 0) return null;
let current = lists.slice();
while (current.length > 1) {
const next: Array<ListNode | null> = [];
for (let i = 0; i < current.length; i += 2) {
next.push(i + 1 < current.length
? mergeTwoLists(current[i], current[i + 1])
: current[i]);
}
current = next;
}
return current[0];
}mergeKLists([[1,4,5],[1,3,4],[2,6]]). What is the output?