Merge k Sorted Lists

hardTests passed 2026-11-11v1.0.0
TC: O(N log k)|SC: O(1)
Linked ListsHeapsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Either push the head of each non-empty list into a size-k min-heap (`O(N log k)` time, `O(k)` space) OR pairwise divide-and-conquer merge halves (`O(N log k)` time, `O(1)` extra heap allocations).

2. Complexity Bounds & Proof

Bottom-up pairwise merging halves k lists per round across log k rounds touching all N total nodes once per round.

3. Minimal Idiomatic Code

def mergeKLists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    if not lists:
        return None
    def merge2(a, b):
        dummy = tail = ListNode()
        while a and b:
            if a.val <= b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a or b
        return dummy.next
    step = 1
    while step < len(lists):
        for i in range(0, len(lists) - step, step * 2):
            lists[i] = merge2(lists[i], lists[i + step])
        step *= 2
    return lists[0]

4. Failure Modes & Interview Follow-ups

Pitfalls:- In Python `heapq`, `(node.val, node)` throws `TypeError` on tie-breaks because `ListNode` lacks `<`; break ties with unique index `i` `(node.val, i, node)` or merge bottom-up in O(1) space.
Follow-ups:- External merge sort on disk streams chunks via a k-way min-heap buffer.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Merge Two Sorted Lists (O(N + M))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.