Merge K Sorted Lists

Interview Prep

HardLinked Listheaplinked-list

The problem

Given a list of k sorted linked lists, merge them into one sorted linked list. Reuse the existing nodes. 

class Node:
    def __init__(self, val: int, next: 'Node | None' = None):
        self.val = val
        self.next = next

Why "merge them pairwise in a loop" is wasteful

Concatenating list 0 with list 1, then merging that with list 2, then list 3 — each merge revisits every node of the result so far. If the lists are balanced in size, this is O(k · N) where N is the total node count. For k = N (lots of small lists), that's quadratic. Two standard fixes get to O(N log k): a min-heap, or divide-and-conquer pairwise merging.

Pattern: k-way merge with a min-heap

The classic external-sort primitive. At any moment, the smallest unused element across all k lists is the head of one of them. A min-heap of size k tracks those heads; extract the min, append it to the output, push its successor. Each of the N nodes participates in one push and one pop: O(N log k).

A subtle gotcha: heaps compare tuples element-by-element. If two heads have equal val, Python will try to compare the Node objects, which aren't comparable. Use the list index i (or any unique tiebreaker) as the second tuple element.

Heap solution

import heapq

def merge_k(lists: list['Node | None']) -> 'Node | None':
    """Min-heap of (val, tiebreaker, node). O(N log k)."""
    heap = []
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))   # i breaks ties on equal vals
    dummy = Node(0)
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    tail.next = None
    return dummy.next

Trace

lists = [1->4->5, 1->3->4, 2->6]
heap initial: [(1, 0, A1), (1, 1, B1), (2, 2, C1)]

pop (1, 0): tail -> 1. push (4, 0, A2).        heap: [(1,1,B1),(2,2,C1),(4,0,A2)]
pop (1, 1): tail -> 1. push (3, 1, B2).        heap: [(2,2,C1),(3,1,B2),(4,0,A2)]
pop (2, 2): tail -> 2. push (6, 2, C2).        heap: [(3,1,B2),(4,0,A2),(6,2,C2)]
pop (3, 1): tail -> 3. push (4, 1, B3).        heap: [(4,0,A2),(4,1,B3),(6,2,C2)]
pop (4, 0): tail -> 4. push (5, 0, A3).        heap: [(4,1,B3),(5,0,A3),(6,2,C2)]
pop (4, 1): tail -> 4. B has no next.          heap: [(5,0,A3),(6,2,C2)]
pop (5, 0): tail -> 5. A has no next.          heap: [(6,2,C2)]
pop (6, 2): tail -> 6. C has no next.          heap: []

result: 1->1->2->3->4->4->5->6

Divide-and-conquer alternative

Pair up the lists, merge each pair (using the standard two-list merge), then repeat on the halved set. After log k rounds, one list remains. Each node is touched in O(log k) rounds × O(1) per touch = O(N log k). Same complexity as the heap, no heap library required. 

def merge_two(a, b):
    dummy = Node(0); tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

def merge_k_divide(lists):
    """Pairwise merge in O(N log k) via divide-and-conquer."""
    if not lists: return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            a = lists[i]
            b = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two(a, b))
        lists = merged
    return lists[0]

Complexity

Variations worth knowing