Problem 22 · Linked Lists

Merge K Sorted Lists

HardClassic DSA & systems

01Problem

Given k sorted linked lists, merge them into one sorted linked list and return its head.

02Key insight

Keep a min-heap of the current head of each list (k entries); pop the smallest, append it, push its successor. A tie-breaker index avoids comparing nodes.

03Solution

solution.pypython20 lines

from __future__ import annotations
import heapq
from dataclasses import dataclass
from typing import Optional

@dataclass
class ListNode:
    val: int
    next: Optional[ListNode] = None

def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)
    dummy = tail = ListNode(0)
    while heap:
        _, i, node = heapq.heappop(heap)
        tail.next = tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

Try it first.

TimeO(N log k)

SpaceO(k)

tests.py · 4 passing

tests.pypython14 lines

def build(vals):
    head = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head
def to_list(node):
    out = []
    while node:
        out.append(node.val); node = node.next
    return out
assert to_list(merge_k_lists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])) == [1, 1, 2, 3, 4, 4, 5, 6]
assert merge_k_lists([]) is None
assert merge_k_lists([None, None]) is None
assert to_list(merge_k_lists([None, build([0])])) == [0]

04Staff-level follow-up

Lists are sorted files too big for memory across many machines? This is the merge phase of external sort: stream buffered blocks per file through the same k-way heap, or merge hierarchically in rounds to bound fan-in and open file handles.