Merge K Sorted Lists

You are given an array of k linked lists, each already sorted in ascending order. Merge them into a single sorted linked list and return its head.

Example#

For lists [[1, 4, 5], [1, 3, 4], [2, 6]] the merged output is 1 to 1 to 2 to 3 to 4 to 4 to 5 to 6. An empty input array returns None.

Brute force note#

Concatenating all nodes and sorting is O(N log N) where N is the total node count, but it ignores the fact that each list is already sorted. Repeatedly scanning all k heads to find the minimum is O(N times k), which is slow when k is large.

Optimal approach#

Use a min-heap holding the current front node of each list, keyed by value. Pop the smallest, append it to the output, and push that node’s next (if any) back into the heap. Repeat until the heap empties. The heap always exposes the global minimum among all list fronts in O(log k) time. Break value ties with the list index so heapq never has to compare nodes directly.

 1import heapq
 2
 3
 4class ListNode:
 5    def __init__(self, val=0, next=None):
 6        self.val = val
 7        self.next = next
 8
 9
10def merge_k_lists(lists):
11    heap = []
12    for i, node in enumerate(lists):
13        if node:
14            heapq.heappush(heap, (node.val, i, node))
15
16    dummy = tail = ListNode()
17    while heap:
18        val, i, node = heapq.heappop(heap)
19        tail.next = node
20        tail = node
21        if node.next:
22            heapq.heappush(heap, (node.next.val, i, node.next))
23    return dummy.next
24
25
26def build(values):
27    head = None
28    for v in reversed(values):
29        head = ListNode(v, head)
30    return head
31
32
33merged = merge_k_lists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])
34out = []
35while merged:
36    out.append(merged.val)
37    merged = merged.next
38print(out)  # [1, 1, 2, 3, 4, 4, 5, 6]

Complexity#

Time is O(N log k) where N is the total number of nodes: each node is pushed and popped once at O(log k). Space is O(k) for the heap, which never holds more than one node per list.

This is a heap-driven k-way merge. Reinforce the top K with heaps pattern, then continue through the 60-day curriculum.