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.