Merge k Sorted Lists
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Merge k sorted linked lists into one sorted list.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Merging two lists was easy: compare the two fronts. With k lists, how can you find the smallest of k fronts quickly?
- Hint 2A heap gives the smallest item in O(log k).
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Five sorted queues of customers, each queue with ascending token numbers. A single clerk wants to call everyone in token order. Only the first person of each queue matters, so he keeps those five front tokens on a small notice board that always tells him the smallest. He calls that person, and the next person from the same queue steps up onto the board.
- The obvious way
Collect all values, sort, rebuild: O(N log N). Or merge lists one after another: up to O(N x k).
- The key insight
Put the first node of each list into a min-heap. Repeatedly pop the smallest node, attach it to the answer, and push that node's next node (if any) into the heap. The heap never holds more than k nodes, so each of the N nodes costs O(log k).
- The algorithm
- Push the head node of every non-empty list into a min-heap.
- Pop the smallest node and attach it to the end of the answer.
- If that node has a next node, push the next node into the heap.
- Repeat until the heap is empty.
Watch it run
Examplelists = [1->4->5, 1->3->4, 2->6]
The board holds the three fronts: 1, 1 and 2. The smallest is a 1: call it.
merged: 1
Where people slip
- In Python add a tie-breaker (like the list index) to the heap tuple: nodes cannot be compared when values are equal.
- Another valid approach is divide and conquer: merge lists in pairs.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
import heapq
# ListNode is provided
def merge_k_lists(lists):
heap = [] # (value, tie-breaker, node)
for index, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, index, node))
dummy = ListNode()
tail = dummy
while heap:
value, index, node = heapq.heappop(heap) # smallest front
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, index, node.next))
return dummy.nextNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.