Free lesson · DSA Mastery - Interview Prep, End to End

Merge k Sorted Lists

Medium8 min readdsaheaps

Merge k Sorted Lists

Merge k Sorted Lists is the purest K-Way Merge: given k sorted linked lists, merge them into one sorted list. A min-heap holding the current head node of each list always yields the next-smallest node; pop it, append to the output, and push its next. It is the canonical, explicit form of the pattern the last two problems used implicitly - the sequences are real linked lists rather than rows or generated pairs - and it is one of the most frequently asked heap problems in interviews. We present the min-heap of heads (canonical) and the divide-and-conquer pairwise merge alternative.

The insight: the global next-smallest node across all lists must be the head of some list, since each list is sorted. A min-heap holding one node - the current head - from each list surfaces that global minimum in O(log k). Pop it, splice it onto the result, and push its successor (next) so the heap always holds exactly one frontier per non-exhausted list. This is the K-Way Merge template in its most literal form.

The Problem

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: Merging them into one sorted list yields 1->1->2->3->4->4->5->6.

Example 2:

Input:  lists = []
Output: []

Constraints:

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

Approaches Overview

The heap approach seeds a min-heap with the head of each list, then repeatedly pops the smallest node, appends it, and pushes its next - N total nodes, each through the heap once. The divide-and-conquer approach pairs lists and merges them two at a time (like merge sort's merge step), halving the list count each round for log k rounds. Both are O(N log k); the heap is the direct K-Way Merge realization, the divide-and-conquer is a neat heap-free alternative.

Approach 1: Min-Heap of Current Heads - Canonical

The Idea

Seed a min-heap (ordered by node value) with the head of each non-empty list. Use a dummy head to build the result. Repeatedly poll the smallest node, append it to the result tail, and if it has a next, push that next onto the heap. When the heap empties, the result list is fully merged.

Logic Flowchart

graph TD
    A["min-heap by node value; push each non-null list head"] --> B["dummy head; tail = dummy"]
    B --> C{"heap not empty?"}
    C -->|No| D["return dummy.next"]
    C -->|Yes| E["node = poll() (smallest head)"]
    E --> F["tail.next = node; tail = node"]
    F --> G{"node.next != null?"}
    G -->|Yes| H["push node.next"]
    G -->|No| I["that list exhausted"]
    H --> C
    I --> C

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style I fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows the heap merge. The heap holds each list's current head; repeatedly the smallest is popped, appended to the result, and its next node pushed, until the heap empties.

Code

// Definition: class ListNode { int val; ListNode next; ListNode(int v){val=v;} }

public static ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
    for (ListNode head : lists)
        if (head != null) heap.offer(head);              // seed one frontier per list

    ListNode dummy = new ListNode(0), tail = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();                     // smallest current head
        tail.next = node;                                // splice onto result
        tail = node;
        if (node.next != null) heap.offer(node.next);    // push successor frontier
    }
    return dummy.next;
}

// Usage:
// mergeKLists([[1,4,5],[1,3,4],[2,6]]) -> 1->1->2->3->4->4->5->6

This Java code seeds a min-heap with each list's head, then repeatedly polls the smallest node, splices it onto a result list via a dummy head, and pushes that node's successor, until the heap is empty.

Step-by-Step Walkthrough

A frame-by-frame trace on lists = [[1,4,5],[1,3,4],[2,6]]:

graph LR
    F0["heap heads: 1(A),1(B),2(C). poll 1(A)→result; push 4(A)"]
    F1["heap: 1(B),2(C),4(A). poll 1(B)→result; push 3(B)"]
    F2["poll 2(C)→push6; poll 3(B)→push4(B); poll 4(A)→push5; poll 4(B)..."]
    F3["...continues → 1,1,2,3,4,4,5,6"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough merges three lists. The heap of current heads yields one, one, two, three, four, four, five, six in order, each pop pushing the next node of that list.

Result: 1->1->2->3->4->4->5->6.

Complexity

Time: O(N log k) - N total nodes, each one heap push/pop of O(log k). Space: O(k) for the heap.

Approach 2: Divide & Conquer Pairwise Merge - Elegant Alternative

The Idea

Merge lists two at a time like merge sort's merge step. Pair up the k lists and merge each pair (a simple two-list merge), halving the count each round. After log k rounds, one merged list remains. Each round touches all N nodes once, and there are log k rounds.

Complexity

Time: O(N log k). Space: O(log k) recursion (or O(1) iterative), no heap.

Complexity Comparison

Both are O(N log k). The heap is the literal K-Way Merge - a min-heap of frontiers producing the merged order directly - and generalizes to streaming or non-list sequences. Divide-and-conquer avoids the heap, uses less auxiliary space, and is a clean recursion, but is specific to mergeable lists. The heap version is the canonical teaching solution for this pattern.

Variations & Follow-ups

Why must the global next-smallest node be the head of some list?

Each list is individually sorted ascending, so within any one list the smallest remaining node is its current head - every later node in that list is >= it. The smallest node across all lists therefore must be one of these per-list heads (it can't be buried deeper in a list, since the head of that list would be even smaller). So holding just the k heads in a min-heap is sufficient to find the global minimum; you never need to look past the front of any list. After removing a head and advancing that list, the new head is the only fresh candidate, which is why one push per pop maintains the invariant. This is the core argument that makes K-Way Merge correct with a heap of only k elements.

Why push only node.next after popping, and why is the heap size bounded by k?

When you pop a list's current head, that list's next-smallest node is its successor node.next - the new front - so that's the single candidate to push. The other lists' heads are already in the heap and unchanged. Because every pop removes one node and pushes at most one (its successor), the heap holds at most one node per list at any time - bounded by k. This keeps each heap operation O(log k) rather than O(log N), which matters when there are many short lists. The one-frontier-per-list invariant is identical to the row-frontier and pair-frontier invariants of the previous two problems; only the sequence representation (linked lists) differs.

Why is the complexity O(N log k) and not O(N log N)?

There are N total nodes, and each is inserted into and removed from the heap exactly once over the whole merge - that's N push/pop pairs. The cost of each heap operation is O(log(heap size)), and the heap never exceeds k elements (one frontier per list), so each operation is O(log k), giving O(N log k) overall. If you instead dumped all nodes into one big heap up front, the heap would hold up to N elements and each operation would be O(log N) - worse when k << N. Maintaining only k frontiers is precisely what keeps the log factor at log k. The divide-and-conquer approach reaches the same O(N log k) by a different counting: log k rounds, each processing all N nodes once.

How does divide-and-conquer achieve the same bound without a heap?

It mirrors merge sort's merge phase: instead of merging all k lists simultaneously, merge them in pairs. Round one merges k/2 pairs into k/2 lists; round two merges those into k/4; after log k rounds, a single sorted list remains. A node participates in one merge per round, and it survives log k rounds, so each node is touched O(log k) times - total O(N log k). The advantage is no auxiliary heap (only O(log k) recursion stack or O(1) iterative), and the two-list merge is simple pointer-splicing. The trade-off is that it's specific to lists you can pairwise-merge, whereas the heap generalizes to any set of sorted streams (including infinite or generated ones).

What about edge cases?

• Empty list array (Example 2): No heads to seed; return null/empty.
• Some lists empty: Skip null heads when seeding; only non-empty lists contribute frontiers.
• Single list: Returned as-is (the heap just drains it in order).
• Duplicate values across lists (Example 1 has two 1s and two 4s): Handled by heap order; duplicates appear consecutively.

Common Interview Pitfalls

• Seeding null heads. Guard against empty lists when offering to the heap.
• Forgetting the dummy head. It simplifies appending the first node and avoids special-casing the result head.
• Pushing the whole list instead of one node. Push only the popped node's next, keeping the heap at size k.
• Comparator on nodes missing. The heap must order by node value, not by object identity.

Why This Topic Matters

Merge k Sorted Lists is the canonical, explicit K-Way Merge and a top interview staple: a min-heap of one frontier per sorted list produces the merged order in O(N log k). It crystallizes the one-frontier-per-sequence invariant used implicitly in the matrix and pair problems, and the divide-and-conquer alternative shows the same bound achieved by pairwise merging - two complementary mergers worth knowing.

The next topic, Smallest Range Covering Elements from K Lists, is a subtler K-Way Merge: find the smallest value range [a, b] that includes at least one number from each of k sorted lists. The technique keeps a min-heap holding one element from every list (and tracks the current maximum among them); the range spanned by the heap's min and the tracked max is a candidate, and you advance by popping the minimum and pushing the next element from its list - shrinking from the low end while every list stays represented. It elevates the frontier idea from "produce merged order" to "maintain one representative per list and optimize a property of the whole frontier," a more advanced use of the pattern that closes the sub-group.

Back to DSA Mastery - Interview Prep, End to End