Hints — p44 Merge K Sorted Lists

Hint 1. Naïve idea: collect all values, sort, rebuild → O(N log N). Works but ignores that each list is already sorted. Can we do O(N log K) where K << N?

Hint 2. Heap-of-K: push the HEAD of each list onto a min-heap. Pop the smallest, append to result, then push its .next (if non-null). Each node enters/leaves heap once → O(N log K).

Hint 3. Python heap GOTCHA — pushing (val, node) blows up on ties:

TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'

because heapq falls through to compare the second tuple element. Fix: push (val, unique_index, node). The index is never compared if values differ; on ties it provides a deterministic order.

Hint 4. Alternative without a heap: DIVIDE AND CONQUER. Pairwise merge the K lists in log K rounds, using a standard merge-two-sorted-lists (LC 21) subroutine. Same O(N log K). Sometimes preferred when you don’t want a heap.

while len(lists) > 1:
    merged = []
    for i in range(0, len(lists), 2):
        l1 = lists[i]
        l2 = lists[i+1] if i+1 < len(lists) else None
        merged.append(merge_two(l1, l2))
    lists = merged
return lists[0]

Hint 5. WHY NOT sequential merge (result = merge(result, lists[i]) for each i)? Round i merges a result of size ~ i · N/K with size N/K. Total = O(N · K). TLE.

Bonus: stdlib has heapq.merge(*iterables) for arbitrary sorted iterables — production one-liner.

If still stuck: see solution.py.