23. Merge k Sorted Lists
Asked at Meta, Apple, Oracle, Rippling and 4 more
Difficulty
Hard
Time
O(N log k)
Space
O(k)
Pattern
Linked List
Companies
8
Problem
You are given an array of k linked lists. Each list is already sorted in ascending order. Your job is to join all of them into a single linked list that is also sorted in ascending order, and return the head of that new list.
You should not create new nodes with new values — just relink the existing nodes into one chain. The result must contain every node from every input list, in sorted order. If a value appears in several lists, it appears that many times in the output.
Edge cases: if the array is empty, or every list inside it is empty, the answer is an empty list (null).
Three sorted lists, one sorted result
Constraints
- ●
k == lists.length - ●
0 <= k <= 10^4 - ●
0 <= lists[i].length <= 500 - ●
-10^4 <= lists[i][j] <= 10^4 - ●
lists[i] is sorted in ascending order - ●
The sum of all lists[i].length is at most 10^4
Examples
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]lists = [][]lists = [[]][]Asked At
8 companies| Company | Difficulty | |
|---|---|---|
| Meta | Hard | View all Meta questions → |
| Apple | Hard | View all Apple questions → |
| Oracle | Hard | View all Oracle questions → |
| Rippling | Hard | View all Rippling questions → |
| Salesforce | Hard | View all Salesforce questions → |
| Walmart | Hard | View all Walmart questions → |
| Bloomberg | Hard | View all Bloomberg questions → |
| NVIDIA | Hard | View all NVIDIA questions → |
How to Think About It
Approach 1 — Naive: merge lists one by one. Merge list 1 and 2, then merge result with list 3, etc. O(N × k) where N is total nodes. Too slow.
Approach 2 — Min-heap: put the head of each list in a min-heap. Extract the smallest, add to result, push its next node. O(N log k) time, O(k) space for heap.
Approach 3 — Divide and conquer: split k lists into halves, merge each half recursively, then merge the two results. O(N log k) time, O(1) extra space (besides recursion).
Why the heap works: the heap always gives you the smallest element across all k lists in O(log k). You build the result one node at a time, always picking the current minimum.
Optimal Approach
Approach 1 — Min-heap:
Step 1: Push the head of each non-empty list into a min-heap (value, list index).
Step 2: Extract the minimum. Add it to the result. If that list has a next node, push it.
Step 3: Repeat until heap is empty.
Approach 2 — Divide and conquer:
Step 1: Split lists into halves recursively until you have pairs.
Step 2: Merge each pair using the merge-two-lists technique.
Step 3: Merge the results upward.
Both approaches: O(N log k) time where N is total nodes. Heap uses O(k) space. Divide-and-conquer uses O(1) extra.
Min-heap picks the smallest head
What Trips People Up in Real Interviews
Merging lists one by one. That's O(nk) where n is total elements and k is number of lists. Using a min-heap is O(n log k).
Not handling empty lists. Some of the k lists might be empty. Skip them or handle them gracefully.
Confusing "merge" with "concatenate and sort." Merging preserves the sorted order without the O(n log n) sort step. Use a heap to always pick the smallest current element.
Forgetting to advance the pointer in the list from which you took the element. After popping from the heap, push the next element from the same list.
Putting all elements in the heap at once instead of just the heads. Inserting all n elements is O(n log n). Inserting only the k heads and pushing one at a time is O(n log k).
Solution Code
O(N log k) timeimport heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
dummy = ListNode()
curr = dummy
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextFrequently Asked Questions
What is the Merge k Sorted Lists problem?
You are given an array of k sorted linked lists. Merge all lists into one sorted list. This problem tests your ability to extend the merge-two-lists pattern using a heap or divide and conquer.
How do you solve Merge k Sorted Lists?
The optimal approach runs in O(N log k) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Merge k Sorted Lists?
Merge k Sorted Lists is asked at Meta, Apple, Oracle, Rippling, Salesforce, Walmart, Bloomberg, NVIDIA. It is a hard difficulty problem.
What are common mistakes on Merge k Sorted Lists?
- Merging lists one by one. That's `O(nk)` where n is total elements and k is number of lists. Using a `min-heap` is `O(n log k)`.
- Not handling empty lists. Some of the `k` lists might be empty. Skip them or handle them gracefully.
- Confusing "merge" with "concatenate and sort." Merging preserves the sorted order without the `O(n log n)` sort step. Use a heap to always pick the smallest current element.
- Forgetting to advance the pointer in the list from which you took the element. After popping from the heap, push the next element from the same list.
- Putting all elements in the heap at once instead of just the heads. Inserting all n elements is `O(n log n)`. Inserting only the k heads and pushing one at a time is `O(n log k)`.