Merge k Sorted Lists
Merge k sorted linked lists into one sorted list and return it.
A way to picture it
k races are finishing at once, each with runners already in finishing order. A referee keeps only the front runner of each race on a podium that always shows the fastest person on top. Crown the top one, and their teammate steps up to replace them.
How to approach it
Push every list's head into a min-heap. Pop the smallest, append it, and push that node's successor. The heap never holds more than k nodes.
Example
Input: {"lists":[[1,4,5],[1,3,4],[2,6]]}. Output: [1,1,2,3,4,4,5,6].
Complexity: O(N log k) time and O(k) space. N total nodes, each costing one heap push and one pop on a heap of size ≤ k.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.