Merge K Sorted Lists
Merge k sorted linked lists into one sorted list.
Why does this pattern fit?
Restate the exact job
Merge k sorted linked lists into one sorted list.
Only the current head of each list can be the next output node.
O(N log k) time · O(k) space
Pushing every node up front loses the streaming advantage.
How to solve Merge K Sorted Lists
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Merge k sorted linked lists into one sorted list.
Why Heaps & ordered selection fits
Only the current head of each list can be the next output node.
State to maintain
A min-heap of list heads and an output tail.
Transition
Pop the smallest head, attach it, and push its successor.
Time and space
O(N log k) time · O(k) space
Counterexample to the tempting mistake
Pushing every node up front loses the streaming advantage.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.