Loading…

hardLinked ListsLC #23Asked very often

Merge k Sorted Lists

Heap & Priority Queue · 5 of 9 · 12 min

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

Merge all the lists into one sorted linked list and return its head.

The result must itself be sorted in ascending order, and it should be built from the existing nodes (you may relink them).

In plain English

We have k independent sorted lists and must produce one globally sorted list. The key realisation is that at every step the next node to emit is the smallest among the current heads of the k lists. The whole problem reduces to repeatedly finding that minimum head efficiently. Doing it by linear scan is O(k) per node → O(N·k); a heap makes it O(log k) per node → O(N log k); divide-and-conquer reaches the same bound by merging lists pairwise in a balanced tree. Some input lists may be empty (null heads) and must be ignored.

Examples

Example 1

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Note: Three sorted lists merged: the two 1s come first, then 2, 3, the two 4s, 5, and 6.

Example 2

Input: lists = []
Output: []
Note: No lists at all → empty result.

Example 3

Input: lists = [[]]
Output: []
Note: A single empty list → empty result. The lone null head is skipped.

Constraints

k == lists.length
0 ≤ k ≤ 10⁴
0 ≤ lists[i].length ≤ 500
-10⁴ ≤ lists[i][j] ≤ 10⁴
Each lists[i] is sorted in ascending order
The sum of lists[i].length will not exceed 10⁴ (this is N)

Clarifying questions4First question: Can any of the k lists be empty, or the whole array be empty?Explore questions

Q1.Can any of the k lists be empty, or the whole array be empty?
Yes — k can be 0, and individual lists can be null. I skip null heads when seeding the heap or recursing, and return null if there's nothing to merge.
Q2.Can I relink the existing nodes, or must I allocate new ones?
I relink the existing nodes into the result — no new value nodes needed beyond a dummy head. That keeps space down to the heap (O(k)) or recursion stack (O(log k)).
Q3.Roughly how do k and N compare? Is k large?
If k is large and N moderate, the heap's O(log k) per node matters. Both my solutions are O(N log k); I'd pick the heap for streaming sources and divide-and-conquer when recursion is fine and I want O(log k) extra space.
Q4.Are duplicate values across lists allowed?
Yes. The merge is stable enough for correctness; in Python I add an index tiebreaker so equal values never force a ListNode comparison.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Two clean O(N log k) solutions (N = total nodes, k = number of lists). (1) Min-heap: push the head of every list into a priority queue keyed by value; repeatedly pop the smallest, append it to a dummy-headed result, and push that node's next. (2) Divide-and-conquer: pair up the k lists and merge each pair with the standard two-list merge, halving the count each round until one list remains. Both beat the naïve 'merge one at a time' O(N·k) by replacing the linear scan for the minimum with either a heap or balanced pairwise merging.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can beat the naïve O(N·k) by recognising this as a k-way merge — and whether you can implement either a heap keyed correctly (comparator / tuple tiebreaker) or a clean divide-and-conquer with the two-list merge as a subroutine.

Where candidates slip

Merging lists one-by-one into an accumulator (O(N·k)), pushing whole ListNodes into a Python heap (TypeError when values tie), or forgetting to skip null/empty input lists.

How to stand out

Name both O(N log k) solutions and compare their trade-offs (heap = O(k) space, streaming-friendly; divide-and-conquer = O(log k) stack, cache-friendly). Derive the complexity out loud and reuse the two-list merge as a named helper.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Min-Heap of List Heads (Optimal)Optimal	`O(N log k)`	`O(k)`	Lead with this when k may be large or sources stream in. Frame it as 'a priority queue always hands me the global minimum head in O(log k)'.	Read
2	Divide and Conquer — Pairwise Merge	`O(N log k)`	`O(log k)`	Offer as the alternative O(N log k) with O(log k) stack and no heap. Frame it as 'merge sort's merge step, but the units are whole sorted lists'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMerge k sorted listsHow to find the next smallest of k heads?Linear scanMin-heap of headsExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Min-Heap of List Heads (Optimal)

TimeO(N log k)SpaceO(k)

Lead with this when k may be large or sources stream in. Frame it as 'a priority queue always hands me the global minimum head in O(log k)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At every step the next node to output is the smallest among the current heads of the k lists. What data structure gives you the minimum of k items and lets you replace it fast?

2Hint 2Explore hint

Seed a min-heap with the head of each non-empty list. Pop the smallest, append it to a dummy-headed result, and if that node has a next, push the next into the heap.

3Hint 3Explore hint

The heap never holds more than k nodes, so each pop/push is O(log k); across all N nodes that's O(N log k). In Python push (val, index, node) so equal values don't compare ListNodes; in Java pass a comparator.

A · Core idea

The merge is driven by one repeated question: of the current front nodes of all k lists, which is smallest? A min-heap answers that in O(log k) and lets us swap in the next candidate just as cheaply.

Why a heap and not a linear scan. The naïve k-way merge scans all k heads to find the minimum each time it emits a node — O(k) per node, O(N·k) overall. A min-heap keeps the k candidate heads partially ordered so the minimum is always at the root (O(1) to read, O(log k) to remove). After we take the smallest node, the only new candidate is that node's successor in its own list, which we push in O(log k). So we replace an O(k) scan with an O(log k) heap op — that single substitution is the whole optimisation.

Why the heap size stays at k. At any instant the heap contains at most one node per list: the current head of each list that still has nodes. We pop one and push at most one (its next), so the size never grows beyond k. That's why the log factor is log k, not log N — a meaningfully tighter bound when k ≪ N.

Why the tiebreaker / comparator matters. When two heads share a value, the heap must still order its entries. In Java, ListNode isn't Comparable, so we must supply a comparator (a, b) -> Integer.compare(a.val, b.val). In Python, heapq compares tuples lexicographically; if we pushed (val, node) and two vals tied, it would fall through to comparing ListNode objects and throw TypeError. Pushing (val, index, node) with a unique index guarantees the comparison resolves on the integer index before it ever touches a node — a subtle but exam-critical detail.

Why the dummy head. As in every list-building problem, a sentinel removes the 'is this the first node?' branch. We append each popped node via curr.next = node; curr = node and return dummy.next. One more detail: the last node we append may still point into its old list, but because we always overwrite curr.next on the next append and the final node's old next was already consumed (or is null), the result is correctly terminated; defensively, you can set curr.next = null at the end.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

lists = [[1, 4, 5], [1, 3, 4], [2, 6]]

Interactive diagram

Heap always surfaces the global minimum head

seed

Active call / nodeSupporting contextReturned stateNot active

The heap holds one live head per list; popping the root and pushing its successor keeps the size at ≤ k.

Final result[1, 1, 2, 3, 4, 4, 5, 6]

C · Code with teaching comments

solution.javaJava

Min-Heap of List Heads (Optimal) — optimal

7 teaching notes

1
import java.util.PriorityQueue;
2
 
3
public class ListNode {
4
    int val;
5
    ListNode next;
6
    ListNode() {}
7
    ListNode(int val) { this.val = val; }
8
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
}
10
 
11
public ListNode mergeKLists(ListNode[] lists) {
12
    // ListNode isn't Comparable, so we MUST supply a comparator ordering by node value.
13
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
14
    for (ListNode node : lists) {
15
        // Skip empty input lists — never push a null head into the heap.
16
        if (node != null) {
17
            pq.offer(node);
18
        }
19
    }
20
    ListNode dummy = new ListNode(0);
21
    ListNode curr = dummy;
22
    while (!pq.isEmpty()) {
23
        // Root of the heap is the global minimum among all current heads — O(log k) to
24
        // remove.
25
        ListNode smallest = pq.poll();
26
        curr.next = smallest;
27
        curr = smallest;
28
        if (smallest.next != null) {
29
            pq.offer(smallest.next);
30
        }
31
    }
32
    // Defensively terminate the result so no stale link from the last node leaks
33
    // through.
34
    curr.next = null;
35
    // Skip the sentinel; return the real merged head.
36
    return dummy.next;
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(N log k) timeO(k) spaceOpen the invariant and proofExplore the proof

The heap converts 'minimum of k things, repeatedly, with cheap replacement' into a logarithmic operation — the defining use case for a priority queue. Recognising that the next output is always the minimum of the live heads is the entire leap; everything else is standard heap mechanics. The same shape appears in Smallest Range Covering Elements and Merge k sorted arrays/iterators.

ComplexityO(N log k) time, O(k) space — Each of the N nodes is pushed once and popped once. The heap size is bounded by k (one live head per list), so each operation costs O(log k). Total = N × O(log k) = O(N log k) time. The heap holds at most k entries → O(k) space (plus the O(1) dummy and pointers).

E · Edge cases and pitfalls7lists = [] — No heads pushed, heap empty, while loop skipped → return dummy.next = null.Explore edge cases

Edge cases handled

lists = []No heads pushed, heap empty, while loop skipped → return dummy.next = null.
lists = [[]]The single head is null → skipped during seeding, heap stays empty → null result.
lists = [[1], [], [0]]Push 1(L0) and 0(L2), skip the empty L1. Pop 0 then 1 → result [0, 1].

Pitfalls

In Python, pushing (val, node) without an index — TypeError when two values tie and heapq compares ListNodes.
In Java, forgetting the comparator — ClassCastException because ListNode isn't Comparable.
Pushing null heads from empty lists — NullPointerException / wrong ordering.
Not terminating the final node's next, leaving a stale link into an old list.

03.2

Approach 2 of 2

Divide and Conquer — Pairwise Merge

TimeO(N log k)SpaceO(log k)

Offer as the alternative O(N log k) with O(log k) stack and no heap. Frame it as 'merge sort's merge step, but the units are whole sorted lists'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already know how to merge TWO sorted lists in O(total) time. How few times do you need to apply that to collapse k lists into one?

2Hint 2Explore hint

Pair the lists up: merge lists[0]+lists[1], lists[2]+lists[3], and so on. That halves the count each round. After log k rounds only one list remains.

3Hint 3Explore hint

Implement it recursively by splitting the array in half, merging each half, then merging the two results — exactly merge sort's structure with sorted lists as the elements.

A · Core idea

Instead of a heap, we lean entirely on the two-list merge and apply it in a balanced binary-tree shape so that each node is merged through only log k levels.

Why pairing beats one-at-a-time. Merging lists sequentially into one accumulator re-walks the growing accumulator over and over: the first list's nodes get compared in every subsequent merge, giving O(N·k). Pairwise merging fixes the imbalance. In round one we merge k/2 independent pairs; in round two k/4 pairs of the results; and so on. A given node participates in one merge per round, and there are only log k rounds — so each node is touched log k times total, yielding O(N log k).

Why it's literally merge sort on lists. Classic merge sort splits an array in half, sorts each half, and merges. Here the 'elements' are already-sorted lists and the 'merge' is the two-sorted-list merge. We recurse on lists[lo..mid] and lists[mid+1..hi], then merge the two returned lists. The recursion tree has depth log k, and the merge work summed across any level is O(N) — the same accounting that gives merge sort its O(n log n).

Why the two-list merge is the heart of it. mergeTwo(a, b) walks both lists with a dummy head, always appending the smaller current node and advancing that list, then attaches whatever remains when one side empties. It runs in O(len(a) + len(b)) and O(1) extra space. Getting this primitive exactly right — the dummy head, the while a and b loop, and the curr.next = a or b tail attach — is what makes the whole divide-and-conquer correct.

Why the space profile differs from the heap. There's no auxiliary heap, so the only extra memory is the recursion stack of depth log k → O(log k). (An iterative version that repeatedly sweeps the array merging adjacent pairs uses O(1) extra.) That makes divide-and-conquer attractive when you want to avoid a heap's O(k) footprint, though both share the same time bound and reuse the same merge subroutine.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

lists = [L0=[1,4,5], L1=[1,3,4], L2=[2,6]]

Interactive diagram

Balanced pairwise merge tree

split

Active call / nodeSupporting contextReturned stateNot active

k lists collapse in log k rounds; each round touches all N nodes once, giving O(N log k).

Final result[1, 1, 2, 3, 4, 4, 5, 6]

C · Code with teaching comments

Reference implementation previewpublic ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return merge(lists, 0, lists.length - 1);Explore the full code

solution.javaJava

Divide and Conquer — Pairwise Merge — reference

7 teaching notes

1
public ListNode mergeKLists(ListNode[] lists) {
2
    // Empty input → nothing to merge, return null before recursing.
3
    if (lists == null || lists.length == 0) {
4
        return null;
5
    }
6
    return merge(lists, 0, lists.length - 1);
7
}
8
 
9
private ListNode merge(ListNode[] lists, int lo, int hi) {
10
    if (lo == hi) {
11
        return lists[lo];
12
    }
13
    // Split the index range in half; overflow-safe form of (lo+hi)/2.
14
    int mid = lo + (hi - lo) / 2;
15
    // Recursively merge the left half of the lists into one sorted list.
16
    ListNode left = merge(lists, lo, mid);
17
    ListNode right = merge(lists, mid + 1, hi);
18
    // Merge the two half-results — this is where log k levels of work accumulate.
19
    return mergeTwo(left, right);
20
}
21
 
22
private ListNode mergeTwo(ListNode a, ListNode b) {
23
    ListNode dummy = new ListNode(0);
24
    ListNode curr = dummy;
25
    // Two-list merge: advance the side with the smaller head, appending as we go.
26
    while (a != null && b != null) {
27
        // <= keeps the merge stable for equal values (a's node first).
28
        if (a.val <= b.val) {
29
            curr.next = a;
30
            a = a.next;
31
        } else {
32
            curr.next = b;
33
            b = b.next;
34
        }
35
        curr = curr.next;
36
    }
37
    // One list is exhausted; attach the entire remaining tail of the other in O(1).
38
    curr.next = (a != null) ? a : b;
39
    return dummy.next;
40
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.40 lines

D · Why it works and complexityO(N log k) timeO(log k) spaceOpen the invariant and proofExplore the proof

Reframing 'merge k lists' as 'merge sort where the elements are sorted lists' instantly delivers the O(N log k) bound and reuses a primitive you already trust. Whenever you see 'combine k sorted things', think balanced pairwise merging or a heap — they're the two faces of k-way merging.

ComplexityO(N log k) time, O(log k) space — There are log k merge rounds. In each round every one of the N nodes is touched exactly once across all the pairwise merges, so each round is O(N). log k rounds × O(N) = O(N log k) time. Recursion depth is log k → O(log k) stack space (the iterative pairwise variant is O(1) extra).

E · Edge cases and pitfalls7lists = [] — Guard returns null immediately — no recursion on an empty range.Explore edge cases

Edge cases handled

lists = []Guard returns null immediately — no recursion on an empty range.
lists = [[1,2,3]]Single list: lo == hi base case returns it unchanged with no merging.
lists = [[], [1], []]mergeTwo treats null halves correctly — merging null with [1] just returns [1]; result [1].

Pitfalls

Merging one list at a time into an accumulator — degrades to O(N·k).
Recursing on an empty range without the lists.length == 0 guard — index errors.
Using < instead of <= in mergeTwo loses stability (cosmetic here, but a habit worth keeping).
Forgetting to attach the leftover tail (curr.next = a or b) — drops the rest of one list.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.PriorityQueue; public class ListNode { int val; ListNode next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Quadratic-ish one-at-a-time merge

Folding lists into a single accumulator re-traverses the growing result on every merge, so early nodes are compared k times — O(N·k). Pairwise merging or a heap brings it to O(N log k).

Explore the code comparison

Don't write this

result = None
for lst in lists:
    result = self._merge_two(result, lst)  # re-walks the accumulator each time
return result

Write this instead

if not lists:
    return None
return self._merge(lists, 0, len(lists) - 1)  # balanced pairwise merges

Pushing ListNodes into a Python heap

heapq compares tuple elements left-to-right; if it reaches a ListNode (because two values tie) it raises TypeError since ListNode defines no ordering. A unique index between val and node resolves ties first.

Explore the code comparison

Don't write this

heapq.heappush(heap, (node.val, node))   # TypeError on equal vals

Write this instead

heapq.heappush(heap, (node.val, i, node)) # index i breaks ties before node

Missing comparator on a Java PriorityQueue

PriorityQueue needs either Comparable elements or an explicit Comparator. ListNode is neither Comparable, so the default constructor throws ClassCastException at the first comparison.

Explore the code comparison

Don't write this

PriorityQueue<ListNode> pq = new PriorityQueue<>(); // ClassCastException

Write this instead

PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Min-heap over list heads OR divide-and-conquer pairwise merge

Code pattern to memorize

# Min-heap (O(N log k))
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapify(heap)
dummy = curr = ListNode(0)
while heap:
    val, i, node = heappop(heap)
    curr.next = node; curr = node
    if node.next:
        heappush(heap, (node.next.val, i, node.next))
return dummy.next

Rules to remember

1Use a dummy head so appending the merged nodes never special-cases the first node.
2Heap holds at most k entries (one live head per list), so each push/pop is O(log k) and total work is O(N log k).
3In Python, push a tuple `(val, index, node)` — the index tiebreaker stops heapq from trying to compare ListNode objects when values tie.
4In Java, give PriorityQueue an explicit comparator (a, b) -> a.val - b.val (or Integer.compare) since ListNode isn't Comparable.
5Divide-and-conquer merges in pairs, halving k each round → log k rounds, each touching all N nodes → O(N log k).
6Skip null lists when seeding the heap or the divide step — an empty input list contributes nothing and a null head must never be pushed/dereferenced.
7Both approaches reuse the two-list merge primitive (Merge Two Sorted Lists) — know it cold.

Use this pattern when

Merge k already-sorted sequences (lists, streams, run files) into one sorted output
k-way merge step of external merge sort
Repeatedly needing the global minimum across k sorted sources → min-heap
Combining results from k shards/partitions that are each locally sorted

Choose another pattern when

Only two lists → just use the single two-pointer merge, no heap needed
Lists are unsorted → sort first, or this k-way trick doesn't apply
Total size is tiny → concatenate-and-sort O(N log N) is simpler and competitive
You need O(1) extra space strictly → divide-and-conquer's recursion is O(log k) stack; heap is O(k)

Interview takeaway

Merge k Sorted Lists is the canonical k-way merge. The min-heap turns 'find the smallest of k heads' into an O(log k) operation; divide-and-conquer gets the same O(N log k) by merging in a balanced binary-tree shape. Both lean on the two-list merge — master that primitive and this hard problem becomes a composition exercise.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical k-way merge. The min-heap variant (O(k) space, streaming-friendly) and the divide-and-conquer variant (O(log k) stack, cache-friendly) both reach O(N log k) and both reduce to the two-list merge primitive. Recognise this shape in external merge sort, Smallest Range Covering Elements, and Kth Smallest in a Sorted Matrix.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Two Sorted Lists
The two-list merge is the primitive both solutions here are built on — master it first.
Merge Sorted Array
Coming soon
Two-way merge on arrays; merge from the back to reuse the destination array in O(1) space.
Smallest Range Covering Elements from K Lists
Coming soon
Same min-heap-of-k-heads engine, but track the current max to shrink a covering range.
Kth Smallest Element in a Sorted Matrix
Coming soon
Each row is a sorted list; a min-heap over row heads is the same k-way merge idea.

Same pattern

←

Task Scheduler

Continue · Next problem

Find K Pairs with Smallest Sums

hardLinked ListsLC #23Asked very often

Merge k Sorted Lists

LCPractice

Heap & Priority Queue · 5 of 9 · 12 min

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

Merge all the lists into one sorted linked list and return its head.

The result must itself be sorted in ascending order, and it should be built from the existing nodes (you may relink them).

In plain English

Examples

Example 1

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Note: Three sorted lists merged: the two 1s come first, then 2, 3, the two 4s, 5, and 6.

Example 2

Input: lists = []
Output: []
Note: No lists at all → empty result.

Example 3

Input: lists = [[]]
Output: []
Note: A single empty list → empty result. The lone null head is skipped.

Constraints

k == lists.length
0 ≤ k ≤ 10⁴
0 ≤ lists[i].length ≤ 500
-10⁴ ≤ lists[i][j] ≤ 10⁴
Each lists[i] is sorted in ascending order
The sum of lists[i].length will not exceed 10⁴ (this is N)

Clarifying questions4First question: Can any of the k lists be empty, or the whole array be empty?Explore questions

Q1.Can any of the k lists be empty, or the whole array be empty?
Yes — k can be 0, and individual lists can be null. I skip null heads when seeding the heap or recursing, and return null if there's nothing to merge.
Q2.Can I relink the existing nodes, or must I allocate new ones?
I relink the existing nodes into the result — no new value nodes needed beyond a dummy head. That keeps space down to the heap (O(k)) or recursion stack (O(log k)).
Q3.Roughly how do k and N compare? Is k large?
If k is large and N moderate, the heap's O(log k) per node matters. Both my solutions are O(N log k); I'd pick the heap for streaming sources and divide-and-conquer when recursion is fine and I want O(log k) extra space.
Q4.Are duplicate values across lists allowed?
Yes. The merge is stable enough for correctness; in Python I add an index tiebreaker so equal values never force a ListNode comparison.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Merging lists one-by-one into an accumulator (O(N·k)), pushing whole ListNodes into a Python heap (TypeError when values tie), or forgetting to skip null/empty input lists.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Min-Heap of List Heads (Optimal)Optimal	`O(N log k)`	`O(k)`	Lead with this when k may be large or sources stream in. Frame it as 'a priority queue always hands me the global minimum head in O(log k)'.	Read
2	Divide and Conquer — Pairwise Merge	`O(N log k)`	`O(log k)`	Offer as the alternative O(N log k) with O(log k) stack and no heap. Frame it as 'merge sort's merge step, but the units are whole sorted lists'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Min-Heap of List Heads (Optimal)

TimeO(N log k)SpaceO(k)

Lead with this when k may be large or sources stream in. Frame it as 'a priority queue always hands me the global minimum head in O(log k)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

At every step the next node to output is the smallest among the current heads of the k lists. What data structure gives you the minimum of k items and lets you replace it fast?

2Hint 2Explore hint

Seed a min-heap with the head of each non-empty list. Pop the smallest, append it to a dummy-headed result, and if that node has a next, push the next into the heap.

3Hint 3Explore hint

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

lists = [[1, 4, 5], [1, 3, 4], [2, 6]]

Interactive diagram

Heap always surfaces the global minimum head

seed

Active call / nodeSupporting contextReturned stateNot active

The heap holds one live head per list; popping the root and pushing its successor keeps the size at ≤ k.

Final result[1, 1, 2, 3, 4, 4, 5, 6]

C · Code with teaching comments

solution.javaJava

Min-Heap of List Heads (Optimal) — optimal

7 teaching notes

1
import java.util.PriorityQueue;
2
 
3
public class ListNode {
4
    int val;
5
    ListNode next;
6
    ListNode() {}
7
    ListNode(int val) { this.val = val; }
8
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
}
10
 
11
public ListNode mergeKLists(ListNode[] lists) {
12
    // ListNode isn't Comparable, so we MUST supply a comparator ordering by node value.
13
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
14
    for (ListNode node : lists) {
15
        // Skip empty input lists — never push a null head into the heap.
16
        if (node != null) {
17
            pq.offer(node);
18
        }
19
    }
20
    ListNode dummy = new ListNode(0);
21
    ListNode curr = dummy;
22
    while (!pq.isEmpty()) {
23
        // Root of the heap is the global minimum among all current heads — O(log k) to
24
        // remove.
25
        ListNode smallest = pq.poll();
26
        curr.next = smallest;
27
        curr = smallest;
28
        if (smallest.next != null) {
29
            pq.offer(smallest.next);
30
        }
31
    }
32
    // Defensively terminate the result so no stale link from the last node leaks
33
    // through.
34
    curr.next = null;
35
    // Skip the sentinel; return the real merged head.
36
    return dummy.next;
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(N log k) timeO(k) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7lists = [] — No heads pushed, heap empty, while loop skipped → return dummy.next = null.Explore edge cases

Edge cases handled

lists = []No heads pushed, heap empty, while loop skipped → return dummy.next = null.
lists = [[]]The single head is null → skipped during seeding, heap stays empty → null result.
lists = [[1], [], [0]]Push 1(L0) and 0(L2), skip the empty L1. Pop 0 then 1 → result [0, 1].

Pitfalls

In Python, pushing (val, node) without an index — TypeError when two values tie and heapq compares ListNodes.
In Java, forgetting the comparator — ClassCastException because ListNode isn't Comparable.
Pushing null heads from empty lists — NullPointerException / wrong ordering.
Not terminating the final node's next, leaving a stale link into an old list.

03.2

Approach 2 of 2

Divide and Conquer — Pairwise Merge

TimeO(N log k)SpaceO(log k)

Offer as the alternative O(N log k) with O(log k) stack and no heap. Frame it as 'merge sort's merge step, but the units are whole sorted lists'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already know how to merge TWO sorted lists in O(total) time. How few times do you need to apply that to collapse k lists into one?

2Hint 2Explore hint

Pair the lists up: merge lists[0]+lists[1], lists[2]+lists[3], and so on. That halves the count each round. After log k rounds only one list remains.

3Hint 3Explore hint

Implement it recursively by splitting the array in half, merging each half, then merging the two results — exactly merge sort's structure with sorted lists as the elements.

A · Core idea

Instead of a heap, we lean entirely on the two-list merge and apply it in a balanced binary-tree shape so that each node is merged through only log k levels.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

lists = [L0=[1,4,5], L1=[1,3,4], L2=[2,6]]

Interactive diagram

Balanced pairwise merge tree

split

Active call / nodeSupporting contextReturned stateNot active

k lists collapse in log k rounds; each round touches all N nodes once, giving O(N log k).

Final result[1, 1, 2, 3, 4, 4, 5, 6]

C · Code with teaching comments

Reference implementation previewpublic ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return merge(lists, 0, lists.length - 1);Explore the full code

solution.javaJava

Divide and Conquer — Pairwise Merge — reference

7 teaching notes

1
public ListNode mergeKLists(ListNode[] lists) {
2
    // Empty input → nothing to merge, return null before recursing.
3
    if (lists == null || lists.length == 0) {
4
        return null;
5
    }
6
    return merge(lists, 0, lists.length - 1);
7
}
8
 
9
private ListNode merge(ListNode[] lists, int lo, int hi) {
10
    if (lo == hi) {
11
        return lists[lo];
12
    }
13
    // Split the index range in half; overflow-safe form of (lo+hi)/2.
14
    int mid = lo + (hi - lo) / 2;
15
    // Recursively merge the left half of the lists into one sorted list.
16
    ListNode left = merge(lists, lo, mid);
17
    ListNode right = merge(lists, mid + 1, hi);
18
    // Merge the two half-results — this is where log k levels of work accumulate.
19
    return mergeTwo(left, right);
20
}
21
 
22
private ListNode mergeTwo(ListNode a, ListNode b) {
23
    ListNode dummy = new ListNode(0);
24
    ListNode curr = dummy;
25
    // Two-list merge: advance the side with the smaller head, appending as we go.
26
    while (a != null && b != null) {
27
        // <= keeps the merge stable for equal values (a's node first).
28
        if (a.val <= b.val) {
29
            curr.next = a;
30
            a = a.next;
31
        } else {
32
            curr.next = b;
33
            b = b.next;
34
        }
35
        curr = curr.next;
36
    }
37
    // One list is exhausted; attach the entire remaining tail of the other in O(1).
38
    curr.next = (a != null) ? a : b;
39
    return dummy.next;
40
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.40 lines

D · Why it works and complexityO(N log k) timeO(log k) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7lists = [] — Guard returns null immediately — no recursion on an empty range.Explore edge cases

Edge cases handled

lists = []Guard returns null immediately — no recursion on an empty range.
lists = [[1,2,3]]Single list: lo == hi base case returns it unchanged with no merging.
lists = [[], [1], []]mergeTwo treats null halves correctly — merging null with [1] just returns [1]; result [1].

Pitfalls

Merging one list at a time into an accumulator — degrades to O(N·k).
Recursing on an empty range without the lists.length == 0 guard — index errors.
Using < instead of <= in mergeTwo loses stability (cosmetic here, but a habit worth keeping).
Forgetting to attach the leftover tail (curr.next = a or b) — drops the rest of one list.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.PriorityQueue; public class ListNode { int val; ListNode next;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Quadratic-ish one-at-a-time merge

Folding lists into a single accumulator re-traverses the growing result on every merge, so early nodes are compared k times — O(N·k). Pairwise merging or a heap brings it to O(N log k).

Explore the code comparison

Don't write this

result = None
for lst in lists:
    result = self._merge_two(result, lst)  # re-walks the accumulator each time
return result

Write this instead

if not lists:
    return None
return self._merge(lists, 0, len(lists) - 1)  # balanced pairwise merges

Pushing ListNodes into a Python heap

Explore the code comparison

Don't write this

heapq.heappush(heap, (node.val, node))   # TypeError on equal vals

Write this instead

heapq.heappush(heap, (node.val, i, node)) # index i breaks ties before node

Missing comparator on a Java PriorityQueue

PriorityQueue needs either Comparable elements or an explicit Comparator. ListNode is neither Comparable, so the default constructor throws ClassCastException at the first comparison.

Explore the code comparison

Don't write this

PriorityQueue<ListNode> pq = new PriorityQueue<>(); // ClassCastException

Write this instead

PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Min-heap over list heads OR divide-and-conquer pairwise merge

Code pattern to memorize

# Min-heap (O(N log k))
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapify(heap)
dummy = curr = ListNode(0)
while heap:
    val, i, node = heappop(heap)
    curr.next = node; curr = node
    if node.next:
        heappush(heap, (node.next.val, i, node.next))
return dummy.next

Rules to remember

1Use a dummy head so appending the merged nodes never special-cases the first node.
2Heap holds at most k entries (one live head per list), so each push/pop is O(log k) and total work is O(N log k).
3In Python, push a tuple `(val, index, node)` — the index tiebreaker stops heapq from trying to compare ListNode objects when values tie.
4In Java, give PriorityQueue an explicit comparator (a, b) -> a.val - b.val (or Integer.compare) since ListNode isn't Comparable.
5Divide-and-conquer merges in pairs, halving k each round → log k rounds, each touching all N nodes → O(N log k).
6Skip null lists when seeding the heap or the divide step — an empty input list contributes nothing and a null head must never be pushed/dereferenced.
7Both approaches reuse the two-list merge primitive (Merge Two Sorted Lists) — know it cold.

Use this pattern when

Merge k already-sorted sequences (lists, streams, run files) into one sorted output
k-way merge step of external merge sort
Repeatedly needing the global minimum across k sorted sources → min-heap
Combining results from k shards/partitions that are each locally sorted

Choose another pattern when

Only two lists → just use the single two-pointer merge, no heap needed
Lists are unsorted → sort first, or this k-way trick doesn't apply
Total size is tiny → concatenate-and-sort O(N log N) is simpler and competitive
You need O(1) extra space strictly → divide-and-conquer's recursion is O(log k) stack; heap is O(k)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Two Sorted Lists
The two-list merge is the primitive both solutions here are built on — master it first.
Merge Sorted Array
Coming soon
Two-way merge on arrays; merge from the back to reuse the destination array in O(1) space.
Smallest Range Covering Elements from K Lists
Coming soon
Same min-heap-of-k-heads engine, but track the current max to shrink a covering range.
Kth Smallest Element in a Sorted Matrix
Coming soon
Each row is a sorted list; a min-heap over row heads is the same k-way merge idea.

Same pattern

←

Task Scheduler

Continue · Next problem

Find K Pairs with Smallest Sums