← Back to DSA Animator
Merge K Sorted Lists LC #23 Hard Linked List · Min-Heap
Problem

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example 1
Input:lists = [[1,4,5],[1,3,4],[2,6]]
Output:[1,1,2,3,4,4,5,6]
Explanation:The three sorted lists are merged into one sorted output.
Example 2
Input:lists = [[1,2],[0,3]]
Output:[0,1,2,3]
Explanation:Always pop the smallest — here 0 from list 1, then 1 from list 0, etc.
Constraints: k == lists.length  |  0 ≤ k ≤ 10⁴  |  0 ≤ lists[i].length ≤ 500  |  −10⁴ ≤ lists[i][j] ≤ 10⁴
Try Examples
Custom:
Min-Heap Merge Visualization
Input Lists
Min-Heap  (0 entries)  [min at top]
Heap is empty
Result List  (0 nodes)
No nodes yet
State Variables
Heap Size
0
Current Min
—
Result Size
0
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Push each list's head into a min-heap (PriorityQueue keyed by value)
2
poll() the minimum node from the heap
3
Append the popped node to the result list
4
If node.next != null, push node.next into the heap
5
Repeat until heap is empty — return dummy.next
Time
O(N log k)
Space
O(k)
Why Min-Heap Works

We maintain a min-heap of size ≤ k — one candidate from each list. Each poll() retrieves the globally smallest remaining node in O(log k). After appending it, we push its successor (if any) so each list always has exactly one representative in the heap. Total nodes processed = N, each heap operation costs O(log k), giving O(N log k).