Merge K Sorted Lists
Merge k sorted linked lists (or arrays) into one sorted list using a min-heap of size k, where each heap entry tracks the current element and its list.
Merge K sorted = K checkout lanes at a grocery store, each already sorted. A tiny elf (the min-heap) always picks the next item from whichever lane has the smallest front item. One elf, K lanes, perfectly sorted output.
Initialize the heap with the first element from each list — O(k log k). Extract the minimum, add it to output, push the next element from the same list — O(log k). Repeat until heap is empty — O(n log k) total, where n is the total number of elements. Alternative: divide-and-conquer (pair-wise merge like mergesort) — O(n log k) time, same complexity but different constant. Sequential merging is O(n*k) — avoid.
The heap approach is optimal: each of the n elements is pushed and popped from the heap exactly once, each operation O(log k), giving O(n log k). This matches the information-theoretic lower bound for this problem. For external merge sort (merging k sorted chunks from disk), this is the standard approach with k = RAM_size / page_size. In Python, heapq.merge() does exactly this lazily (using a heap internally) with O(1) memory beyond the iterators. For the linked list variant, store (value, list_index, node_pointer) in the heap to handle ties and track which list to advance.
Merge k sorted lists is a direct application of a min-heap. I initialize the heap with the head of each list, then repeatedly extract the minimum and advance that list. O(n log k) time — each of the n elements is heap-inserted exactly once. I'd also mention the divide-and-conquer alternative: merge lists in pairs, like bottom-up mergesort — also O(n log k) but O(log k) levels of merging. For interviews, the heap approach is more straightforward to implement and explain.
When using Python's heapq with custom objects (linked list nodes), you can't directly compare nodes if values are equal — Python will try to compare the ListNode objects and fail. Store tuples (value, index, node) where index is a tie-breaker. Forgetting the tie-breaker causes a TypeError when two nodes have equal values.