Merge K Sorted Lists

Problem

Database engines and distributed systems merge sorted partitions (from different shards or sort runs) into a single sorted result. This is the K-way merge problem: the naive approach collects everything and sorts, but a heap does it in O(n log K) by always knowing which list holds the next global minimum. Given k sorted linked lists, return one sorted merged linked list.

Input: [[1->4->5], [1->3->4], [2->6]]   → 1->1->2->3->4->4->5->6
Input: []   → []
Input: [[]]   → []

Solution

Approach: K-way merge with a min-heap.

Each input list is already sorted, so at any moment the next node for the output is the smallest current head across the K lists. A min-heap finds that minimum in O(log K). Seed it with one entry per non-empty list as (node.val, i, node): the value drives ordering, and i (the list index) is a tie-breaker that stops Python from ever comparing two ListNode objects when values are equal - direct node comparison raises TypeError. Then loop: pop the smallest entry, splice its node onto the result via a dummy-head cursor, and if that node has a successor, push (node.next.val, i, node.next). Each pop emits the global minimum among all remaining heads, so the output is built in sorted order. The heap holds at most one node per list, and every node is pushed and popped exactly once.

The dummy head lets the first attachment use the same curr.next = node; curr = curr.next step as every other, with the merged list read off as dummy.next at the end.

Edge cases: an empty lists, or lists that are all None, push nothing, so the loop never runs and dummy.next is None. A list exhausting simply contributes no further pushes; the heap shrinks until empty.

Complexity: O(n log K) time, O(K) space - n total nodes, each an O(log K) heap operation against a heap bounded by the K list count.