Merge k Sorted Lists
On this page
Problem statement
Given k sorted linked lists, merge them all into one sorted linked list and return its head. Any of the lists may be empty, and k may be zero.
The natural extension of Merge Two Sorted Lists, and a classic heap question. It's also how databases and log systems merge many sorted runs. Original problem: LeetCode 23.
Example

Input: [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Input: []
Output: null
Constraints (assumed)
- 0 ≤ k ≤ 10,000; total nodes N ≤ 10,000.
- Each list sorted ascending.
What this question tests
- Generalizing a two-way merge to k ways efficiently.
- Using a heap to always find the smallest of k candidates in O(log k).
- Comparing with divide and conquer and explaining why one-by-one merging is slow.
Questions to ask first
- Can lists be empty, and can k be 0? (Here: yes to both.)
- Can I reuse the nodes? (Here: yes.)
- Roughly how big are k and N? It decides whether the log k factor matters.
- Is the merge required to be stable for equal values? Usually not; tie-break by list index if so.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.