Merge K Sorted Lists
FreeLinked listsHard24 of 75
The problem
Merge k ascending singly linked lists into one ascending list. Inputs may contain empty lists.
Example
[1 → 6, 2 → 4, 3 → 5] becomes 1 → 2 → 3 → 4 → 5 → 6
Need a hint?
Only the head of each remaining list can be the next smallest node.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Put each nonempty head in a min-heap with a tie-breaking counter so equal values do not compare node objects. Pop the smallest node, append it, and push its successor. Repeat until the heap is empty.
Complexity
O(N log k) time and O(k) auxiliary space for N total nodes (k ≥ 2).
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.