Given k sorted linked lists, merge them into one sorted linked list and return it.
Before you code
Merging the lists one after another costs O(N × k) in the worst case. The smallest remaining node is always one of the k current heads, and a heap finds it in O(log k).
Hints
- Push
(value, list_index, node)for each non-empty list; the index breaks ties, so nodes are never compared. - Pop the smallest, append it to the result behind a dummy head, and push that node's next, if any.
- Alternative with the same complexity: merge the lists in pairs, halving their number each round.
Production & complexity notes
When solving Merge k sorted lists on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Top-k and merging streams to reinforce the underlying pattern.
What it practices
The k-way merge, from Top-k and merging streams.