progress

~/problems / Heaps / Heaps and priority queues

Merge K Sorted Lists

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~35 min

Write merge_k_lists(lists). lists is a Python list of linked-list heads (ListNode or None), each sorted in non-decreasing order. Return the head of a single sorted linked list made by splicing together all the original nodes (don't allocate new value nodes; a dummy head is fine).

lists = [ 1 -> 5 -> 6,   2 -> 3,   None,   0 -> 5 ]
result:  0 -> 1 -> 2 -> 3 -> 5 -> 5 -> 6

lists = []        result: None
lists = [None]    result: None

Up to 40,000 lists and 120,000 nodes.

⭐ Bonus: a speed test with 2,000 lists earns a star in O(N log k) (N total nodes). Merging the lists into an accumulator one at a time is O(N·k).

Show hint

At every step the next output node is the smallest of the k current fronts. Keep the fronts in a structure that finds and replaces the smallest in O(log k). ListNode objects can't be compared, so give ties something comparable to fall back on.

Topic: Heaps and priority queues. heapq: top-k, k-way merge, two heaps for a running median.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc