Merge k Sorted Lists
Asked at Meta, Apple, Oracle, Rippling, Salesforce, Walmart
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.
Asked At
| 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 → |
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.
Visual walkthrough for lists: [1→4→5], [1→3→4], [2→6]:
Heap: [(1,list1), (1,list2), (2,list3)]
Extract 1 (list1). Push 4. Heap: [(1,list2), (2,list3), (4,list1)].
Extract 1 (list2). Push 3. Heap: [(2,list3), (3,list2), (4,list1)].
Extract 2 (list3). Push 6. Heap: [(3,list2), (4,list1), (6,list3)].
Extract 3 (list2). Push 4. Heap: [(4,list1), (4,list2), (6,list3)].
Extract 4 (list1). Push 5. Heap: [(4,list2), (5,list1), (6,list3)].
Extract 4 (list2). Next null. Heap: [(5,list1), (6,list3)].
Extract 5 (list1). Next null. Heap: [(6,list3)].
Extract 6 (list3). Next null. Heap empty.
Result: 1→1→2→3→4→4→5→6.
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.
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
import 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Merge k Sorted Lists?
Merge k Sorted Lists is asked at Meta, Apple, Oracle, Rippling, Salesforce, Walmart. 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)`.