Merge k Sorted Lists

LeetCode 23 • Hard • Linked Lists / Heaps

Input: lists = [[1,4,5],[1,3,4],[2,6]] → Output: [1,1,2,3,4,4,5,6]. Min-heap of k heads. Pop min, append, push next. O(n log k).

TimeO(n log k)

SpaceO(k)

Heap: [] Result: []

Min-heap

Result

Current head

heap[]

result[]

Speed:

Ready

Press Play. Min-heap stores (val, listIdx). Pop min, append to result, push next from that list.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Min-heap of list heads.

═══ MERGE K SORTED LISTS — MIN-HEAP ═══

PATTERN ▸ Min-heap of k heads O(n log k) · O(k)

① INIT

heap = [(l.val, i) for i, l in enumerate(lists) if l]

heapq.heapify(heap)

② LOOP

while heap: val, i = heapq.heappop(heap)

append val to dummy; if lists[i].next: heappush(heap, (lists[i].next.val, i)); lists[i] = lists[i].next

③ RETURN

return dummy.next

your implementation

Verify: