Merge k Sorted Lists

This is the classic "one entry per source" heap problem, and it is rated hard mostly because of one detail: equal values. Get the tie-breaker right and the rest is a short loop.

The problem

You are given k linked lists. Each list is already sorted in ascending order. Merge them all into one sorted linked list and return its head. Let N be the total number of nodes across all lists.

• Lists 2 → 6 → 9, 1 → 4 → 9, 3 → 5 → 1 → 2 → 3 → 4 → 5 → 6 → 9 → 9.
• An empty input, or k lists that are all empty → an empty list (None).

Constraints: 0 ≤ k ≤ 10⁴, each list has up to 500 nodes, N ≤ 10⁴, values between -10⁴ and 10⁴.

Clarifying questions

• May I reuse the existing nodes? Yes; relinking them is expected and saves memory.
• Can a list be empty (None)? Yes, any of them.
• Are values unique? No, duplicates happen, within a list and across lists.

Approach 1: collect and sort, or merge one list at a time

The quickest correct answer copies every value out, sorts, and builds a new list: O(N log N) time and O(N) extra space. It ignores the fact that each list is already sorted.

A second simple answer reuses the two-list merge from the Linked Lists section and folds the lists in one at a time:

1from typing import Optional23class ListNode:4    def __init__(self, val: int, next: Optional["ListNode"] = None) -> None:5        self.val = val6        self.next = next78def merge_two(a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:9    """Standard merge of two sorted lists, reusing their nodes."""10    dummy = ListNode(0)11    tail = dummy12    while a is not None and b is not None:13        if a.val <= b.val:14            tail.next, a = a, a.next15        else:16            tail.next, b = b, b.next17        tail = tail.next18    tail.next = a if a is not None else b19    return dummy.next2021def merge_k_one_by_one(lists: list[Optional[ListNode]]) -> Optional[ListNode]:22    """Fold the lists in one at a time: result = merge(result, next list)."""23    result: Optional[ListNode] = None24    for head in lists:25        result = merge_two(result, head)26    return result

Why it is slow: the growing result is walked again on every merge. If each list has N/k nodes, merge number i walks about i × N/k nodes. Summed over k merges that is about k × N / 2, so O(kN). With k = 10⁴ one-node lists, that is about 5 × 10⁷ node visits — too slow in Python, and almost all of it is walking the same early nodes again.

The key insight

At every moment, the next node of the output is the smallest of the k current heads. Nothing further down any list can be smaller, because every list is sorted. So you only ever need to compare k candidates, one per list.

"Give me the smallest of k changing candidates" is exactly a min-heap of size k. Pop the smallest head, attach it to the output, and push that node's successor — the new head of the same list. The heap never holds more than k entries, so each step costs O(log k) instead of walking a long list.

The one trap is ties. The heap entry must be a tuple whose first field is the value. If two heads have the same value, Python compares the next field. If that field is the node, it raises TypeError: '<' not supported between instances of 'ListNode'. So put a unique number — the list's index — between the value and the node.

Approach 2: a min-heap of heads

1import heapq2from typing import Optional34def merge_k_heap(lists: list[Optional[ListNode]]) -> Optional[ListNode]:5    """Hold the current head of every list in a min-heap; always take the smallest."""6    heap: list[tuple[int, int, ListNode]] = []7    for index, head in enumerate(lists):8        if head is not None:9            heapq.heappush(heap, (head.val, index, head))   # index breaks ties10    dummy = ListNode(0)11    tail = dummy12    while heap:13        _, index, node = heapq.heappop(heap)14        tail.next = node15        tail = node16        if node.next is not None:17            heapq.heappush(heap, (node.next.val, index, node.next))18    return dummy.next

Dry run on lists 0: 2 → 6 → 9, 1: 1 → 4 → 9, 2: 3 → 5. Heap entries are shown as (value, list).

The last two rows are the tie: both heads are 9, and the list index (0 before 1) decides the order without ever comparing nodes.

Complexity. Every one of the N nodes is pushed once and popped once, on a heap of at most k entries: O(N log k) time. Space O(k) for the heap; the output reuses the input nodes.

Approach 3: merge in pairs

A different way to reach O(N log k) without a heap: merge list 0 with 1, 2 with 3, and so on. That halves the number of lists. Repeat until one is left.

1def merge_k_pairs(lists: list[Optional[ListNode]]) -> Optional[ListNode]:2    """Merge the lists in pairs, round after round, until one is left."""3    if not lists:4        return None5    current = list(lists)6    while len(current) > 1:7        merged = []8        for i in range(0, len(current), 2):9            second = current[i + 1] if i + 1 < len(current) else None10            merged.append(merge_two(current[i], second))11        current = merged12    return current[0]

Each round touches every node once, O(N), and there are log₂ k rounds, so the total is O(N log k) — the same as the heap. It needs O(k) space for the list of heads (or O(1) if you merge in place in the input array). The heap version is easier to extend to streams; the pairwise version has no tuple-tie trap.

Edge cases

• lists is empty, or every list is None: the heap starts empty, the loop never runs, and dummy.next is None.
• One list: it is returned node by node, unchanged.
• Equal values across lists: handled by the index tie-breaker.
• Very unequal lengths: a list that ends simply stops pushing; the others carry on.

Follow-ups

• "The inputs are sorted arrays, not lists." Store (value, array index, position) and push position + 1 from the same array.
• "The lists are huge files on disk." This is the external merge-sort step: the heap holds one buffered head per file, O(k) memory however large the files are.
• "Find the smallest range that includes at least one number from each list." Keep one head per list in a min-heap and track the current maximum; the range is [heap root, current max]. Advance the list whose head was the minimum.