DSA Merging K Sorted Lists

The problem

Merge K Sorted Lists weaves many sorted linked lists into one sorted list. A linked list is a chain of nodes. Each node holds a value and a pointer to the next node.

Every input list is already sorted on its own. The merged list must hold every value from every list, in sorted order. No value is dropped and none is added.

cases = [
    ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
    ([[1, 4, 5], [1, 3, 4], [2, 6], [0, 7], [1, 2]], [0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7]),
    ([], []),
    ([[], [1]], [1]),
]
for lists, expected in cases:
    print("lists", lists, "->", expected)

The cases print lists as plain rows for reading. The real solutions below rebuild each row as a chain of nodes first. The second row merges five lists and twelve values in total.

Intuition: only the heads can come next

The head of a list is its first node. The head holds the smallest value that list still has, because each list is sorted. Every later value hides behind its head.

So the next merged value is always one of the current heads. The smallest head wins the next place. That single observation drives both solutions in this article.

lists = [[1, 4], [2, 3], [0, 5]]
heads = [lst[0] for lst in lists]
print("heads:", heads)
print("smallest head:", min(heads))
print("values hidden behind heads:", [lst[1:] for lst in lists])

The values 4, 3 and 5 cannot come next, whatever their size. Each must wait for its own head to leave first. Only three values compete at any moment, one per list.

Brute force: scan every head for each output value

The brute force follows the intuition literally. It scans all current heads, takes the smallest, advances that list by one node, and repeats. Pointers track how far each list has been read, so no list is copied.

A counter records every head examined. Five lists with twelve values make the scan cost visible at once.

def merge_brute(lists):
    positions = [0] * len(lists)
    merged = []
    examined = 0
    remaining = sum(len(lst) for lst in lists)
    while remaining:
        best = None
        for idx, lst in enumerate(lists):
            if positions[idx] < len(lst):
                examined += 1
                if best is None or lst[positions[idx]] < lists[best][positions[best]]:
                    best = idx
        merged.append(lists[best][positions[best]])
        positions[best] += 1
        remaining -= 1
    return merged, examined

lists = [[1, 4, 5], [1, 3, 4], [2, 6], [0, 7], [1, 2]]
merged, examined = merge_brute(lists)
print("merged:", merged)
print("heads examined:", examined)

Twelve output values cost 48 head examinations. Every output pays for a fresh scan of every live list. More lists means a longer scan behind every single value.

The optimal solution: a heap holding each list's current head

The method in one sentence: keep one heap entry per list, holding that list's current head, and the heap top is always the smallest head. A tie-break is an extra field that decides the order of equal entries, and each entry here carries its list index as the tie-break.

Each pop takes the smallest head and appends its node to the answer. The popped node's own next node then enters the heap. The tie-break also protects the code, because Python cannot order two nodes against each other.

import heapq

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def merge(lists):
    heap = []
    pushes = 0
    for idx, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.value, idx, head))
            pushes += 1
    dummy = Node(0)
    tail = dummy
    pops = 0
    while heap:
        value, idx, node = heapq.heappop(heap)
        pops += 1
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.value, idx, node.next))
            pushes += 1
    return dummy.next, pushes, pops

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

cases = [
    ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
    ([[1, 4, 5], [1, 3, 4], [2, 6], [0, 7], [1, 2]], [0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 7]),
    ([], []),
    ([[], [1]], [1]),
]
for raw, expected in cases:
    merged, pushes, pops = merge([build(values) for values in raw])
    result = to_list(merged)
    print("lists", raw, "->", result, "match:", result == expected, "pushes:", pushes, "pops:", pops)

All four cases pass, including the empty ones. Twelve nodes produce twelve pops. Pushes match the starting heads plus every follow-up node that entered after a pop.

Walkthrough: merging [1, 4], [2, 3] and [0, 5]

The walk merges three short lists. The state is the heap of heads, printed sorted for reading. Each step pops the smallest head and pushes that list's next node.

import heapq

lists = [[1, 4], [2, 3], [0, 5]]
positions = [0, 0, 0]
heap = []
for idx, lst in enumerate(lists):
    heapq.heappush(heap, (lst[0], idx))
merged = []
print("start - heap:", sorted(heap))
while heap:
    value, idx = heapq.heappop(heap)
    merged.append(value)
    positions[idx] += 1
    if positions[idx] < len(lists[idx]):
        heapq.heappush(heap, (lists[idx][positions[idx]], idx))
    print("popped", value, "from list", idx, "- merged:", merged, "- heap:", sorted(heap))

The value 0 leaves first, and its list answers with 5. The value 5 then waits in the heap while 1, 2, 3 and 4 leave. The merged list is read off the pops in order.

Complexity

Let N be the total node count and k the list count. The brute force scans up to k heads per node, so its time is O(N k). The heap pays one pop and at most one push per node, each inside a heap of size k, so its time is O(N log k).

The brute force stores only its position counters, so its extra space is O(k). The heap holds one entry per list, so its extra space is also O(k), and the merged list itself is the output rather than extra space.

for k in (3, 5, 10):
    nodes = 12
    print("lists", k, "- brute head checks at most for 12 nodes:", nodes * k, " heap size never above:", k)

Counts beat clocks here. Doubling the list count doubles the brute scan behind every node. The heap only deepens by one level when the list count doubles.

Edge cases and pitfalls

Equal heads are the classic trap. Two entries with the same value make Python compare the next field. Without the list index, that next field is a node, and comparing nodes raises an error instead of merging.

Empty input is real input here. No lists at all, and lists that are all empty, both merge to an empty list. A single list passes through unchanged.

import heapq

class Node:
    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt

heap = []
try:
    heapq.heappush(heap, (5, Node(5)))
    heapq.heappush(heap, (5, Node(5)))
    print("no error")
except TypeError as e:
    print("TypeError:", e)

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def merge(lists):
    heap = []
    for idx, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.value, idx, head))
    dummy = Node(0)
    tail = dummy
    while heap:
        value, idx, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.value, idx, node.next))
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

print("no lists:", to_list(merge([])))
print("all empty:", to_list(merge([build([]), build([])])))
print("one list:", to_list(merge([build([2, 4, 9])])))
print("empty lists mixed in:", to_list(merge([build([]), build([1, 3]), build([])])))

The error line is the lesson in one line. The index field sits between the value and the node. Equal values settle on the index, and the nodes are never compared.