DSA AnimatorDSA animations
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)
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).

How to solve Merge K Sorted Lists

LeetCode 23 · Hard · Linked List · Pattern: Heap Merge

Why the obvious approach is slow

Merging the lists one by one into the result costs O(k) times n in total. A min heap always knows the smallest head.

The key idea

Put the head of each list into a min heap. Pop the smallest node, attach it to the result, and push its next node if it exists. Repeat until the heap is empty.

Remember

A heap of size k holds one candidate from each list. Each pop gives the next smallest node.

Run the animation above on your own input, or watch the 1:10 video explanation of Merge K Sorted Lists with a dry run and Java code.

More Linked List problems