Merge K Sorted Lists

Problem

You are given an array lists containing the heads of k singly linked lists, each sorted in non-decreasing order. Merge all of them into one sorted linked list and return its head. Nodes should be reused, not copied.

• There are between 0 and 20,000 lists.
• Each list has between 0 and 1,000 nodes; the total number of nodes N is at most 50,000.
• Node values fit in a signed 32-bit integer.

Examples

• lists = [[2, 7, 9], [3, 7, 8], [1, 10]] → [1, 2, 3, 7, 7, 8, 9, 10]. The two 7s both appear; the 10 waits until every other list is drained.
• lists = [[5], [], [4, 6]] → [4, 5, 6]. An empty list in the middle contributes nothing and must not break the merge.
• lists = [] → []. No lists at all.

Hints

1. Merging two sorted lists is easy. What goes wrong if you merge list 1 into list 2, then the result into list 3, and so on?
2. At every step the next output node is the smallest of the k current heads. Which structure gives you "smallest of k things" and lets you replace one of them cheaply?
3. A min-heap of (value, tiebreaker, node) with one entry per non-empty list; pop the min, append it, push its successor. Alternatively, merge pairs of lists in a tournament (divide and conquer).