Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Merge k Sorted Lists
• Main tags: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort

What the problem is really asking

Each input list is already sorted. The task is to combine all of them into one final sorted linked list without losing that order.

The important simplification is that, at any moment, only one node from each list can possibly be the next answer node: the current head of that list.

So this is not really about sorting from scratch. It is a k-way merge problem.

If there are k lists and N total nodes across all of them, the goal is to keep choosing the smallest available head until every node has been appended to the result.

The natural baselines

Two straightforward ideas usually come up first:

• collect every value, sort everything again, and rebuild a list
• repeatedly scan all current list heads to find the smallest next node

Both work, but neither uses the structure of the input well.

Flatten-and-sort costs O(N log N), which throws away the fact that each list is already sorted.

Scanning all k heads for every output node costs O(Nk). That is better than re-sorting in some cases, but it still does too much repeated work because the same heads get compared over and over.

The key insight

The next output node must be the minimum among the current heads of the non-empty lists.

That means the problem reduces to one repeated operation:

• keep track of up to k candidate heads
• extract the smallest one quickly
• when a node is removed from a list, insert that list’s next node as the new candidate

That viewpoint leads to two optimal O(N log k) strategies:

• a min-heap that always gives the smallest current head in O(log k) time
• divide and conquer, where pairs of sorted lists are merged in balanced rounds

How to derive the optimal solution

Start from the slower head-scanning approach.

It already has the right high-level idea: at each step, the answer is one of the current heads. The problem is only that finding the smallest head costs O(k) every time.

A min-heap fixes exactly that bottleneck. Put the current head of each non-empty list into the heap. Now the smallest head can be removed in O(log k) time, and the next node from that same list can be inserted in another O(log k) time.

Each node enters the heap once and leaves the heap once, so the total cost becomes:

• Time: O(N log k)
• Extra space: O(k)

There is another equally good way to reach the same time bound.

If merging two sorted linked lists takes linear time, then the lists can be merged in pairs like merge sort:

1. merge list 0 with list 1, list 2 with list 3, and so on
2. now there are roughly half as many lists
3. repeat until only one list remains

Each round touches every node once, and there are O(log k) rounds, so the total is again O(N log k).

Best approaches

The heap solution is the best default interview answer because it directly matches the “pick the smallest current head” idea and stays efficient even when the lists have very different lengths.

The divide-and-conquer solution is equally strong asymptotically and is a great fallback when the interviewer asks to avoid a heap. It often uses less auxiliary memory, especially in an iterative implementation, but the merging rounds can feel slightly less immediate than the heap model.

The practical rule of thumb is:

• use a min-heap when you want the cleanest k-way merge
• use divide and conquer when you want the same big-O time without heap machinery

Python solution

from heapq import heappop, heappush
from itertools import count
from typing import List, Optional


# LeetCode provides the ListNode class.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class HeapBasedSortedListMerger:
    """Merge multiple sorted linked lists with a min-heap of current heads."""

    def merge(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        min_heap: list[tuple[int, int, ListNode]] = []
        entry_counter = count()

        for node in lists:
            self._push_node(
                min_heap=min_heap,
                entry_counter=entry_counter,
                node=node,
            )

        dummy_head = ListNode(0)
        merged_tail = dummy_head

        while min_heap:
            _, _, smallest_node = heappop(min_heap)
            next_node = smallest_node.next

            merged_tail.next = smallest_node
            merged_tail = merged_tail.next

            # Detach the appended node so the merged chain grows deliberately.
            merged_tail.next = None

            self._push_node(
                min_heap=min_heap,
                entry_counter=entry_counter,
                node=next_node,
            )

        return dummy_head.next

    @staticmethod
    def _push_node(
        min_heap: list[tuple[int, int, ListNode]],
        entry_counter: count,
        node: Optional[ListNode],
    ) -> None:
        if node is None:
            return

        # The counter breaks ties when two nodes have the same value.
        heappush(min_heap, (node.val, next(entry_counter), node))


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        merger = HeapBasedSortedListMerger()
        return merger.merge(lists)

Why this works

The heap always contains exactly the nodes that are eligible to be chosen next: one current head per non-empty list.

When the smallest node is removed, that node is definitely the next value in the global sorted order because every other remaining candidate head is greater than or equal to it, and every later node in the same list is also greater than or equal to it.

After appending that node, the only new candidate that matters is its successor from the same list. Adding that successor restores the same invariant for the next step.

That invariant is what makes the algorithm correct from start to finish.

Interview follow-ups

How would you solve it without a heap?

Use divide and conquer. Repeatedly merge the lists in pairs until only one merged list remains. Since merging two sorted lists takes linear time in their combined length, each round costs O(N), and there are O(log k) rounds because the number of lists is roughly halved each time.

This works because every node still participates in only one merge per round, so the total work stays balanced instead of repeatedly rescanning all list heads. The tradeoff is that the code shifts from a direct k-way merge to a sequence of 2-way merges, which some candidates find less intuitive even though the asymptotic cost is the same.

What if the interviewer asks for O(1) extra space beyond a few pointers?

Then the heap is no longer the best choice because it stores up to k heads. An iterative divide-and-conquer merge is the better answer. Merge adjacent pairs in place, double the merge interval each round, and keep rewiring existing next pointers instead of allocating extra structures.

That approach still runs in O(N log k) time, and its working memory stays constant apart from a handful of pointer variables. The tradeoff is that the implementation is more pointer-heavy, so it is easier to make mistakes unless the merge helper for two lists is already solid.

What if the lists are extremely unbalanced, with one huge list and many tiny ones?

The heap solution still behaves well. Every node is processed once, and every heap operation depends on k, not on the size of the largest list. That means one huge list does not fundamentally change the O(N log k) bound.

The main tradeoff is in constant factors. A divide-and-conquer strategy can sometimes do slightly better or worse depending on how the merge rounds line up, while the heap solution keeps the work pattern very stable. In an interview, that makes the heap answer the safer default when list sizes are unpredictable.

What if the interviewer wants nodes produced lazily instead of returning one finished list at the end?

The same heap idea can be turned into a streaming merge. Instead of linking nodes into one result list immediately, the algorithm can yield the smallest node or value each time it is popped from the heap, then push the next node from that list.

This works because the ordering guarantee comes from the heap invariant, not from the fact that a final linked list is materialized. The complexity remains O(log k) per emitted node with O(k) extra space. The tradeoff is that a streaming interface is great for pipelines or early stopping, but it does not match LeetCode’s required return type.

Practical takeaway

The fastest way to understand this problem is to stop thinking about all N nodes and focus on the k current heads.

Once that shift happens, the rest follows naturally: the problem is just repeated extraction of the smallest current head, and a min-heap is built for exactly that job.