Skip to content

Merge K Sorted Lists

Problem

Given an array of k sorted linked lists, merge them into one sorted linked list.

Approach

Use a min-heap of size k. Push (value, list_index, node) tuples. Pop the smallest, append to result, and push the next node from that list. The list_index breaks ties to avoid comparing nodes.

When to Use

K-way merge for external sorting — "merge K sorted lists/arrays/files", combining sorted partitions from distributed systems. Min-heap of size k selects the next smallest element. See also: merge_two_sorted.

Complexity
Time O(n log k) where n = total nodes across all lists
Space O(k) for the heap

Implementation

merge_k_sorted_lists

Merge k sorted linked lists.

Problem

Given an array of k sorted linked lists, merge them into one sorted linked list.

Approach

Use a min-heap of size k. Push (value, list_index, node) tuples. Pop the smallest, append to result, and push the next node from that list. The list_index breaks ties to avoid comparing nodes.

When to use

K-way merge for external sorting — "merge K sorted lists/arrays/files", combining sorted partitions from distributed systems. Min-heap of size k selects the next smallest element. See also: merge_two_sorted.

Complexity

Time: O(n log k) where n = total nodes across all lists Space: O(k) for the heap

from_list 

from_list(vals: list[int]) -> ListNode | None

Build a linked list from a Python list.

Source code in src/algo/heaps/merge_k_sorted_lists.py 
64
65
66
67
68
69
70
71
def from_list(vals: list[int]) -> ListNode | None:
    """Build a linked list from a Python list."""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next

merge_k_sorted 

merge_k_sorted(
    lists: list[ListNode | None],
) -> ListNode | None

Merge k sorted linked lists into one sorted linked list.

to_list( ... merge_k_sorted( ... [from_list([1, 4, 5]), from_list([1, 3, 4]), from_list([2, 6])] ... ) ... ) [1, 1, 2, 3, 4, 4, 5, 6]

Source code in src/algo/heaps/merge_k_sorted_lists.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def merge_k_sorted(lists: list[ListNode | None]) -> ListNode | None:
    """Merge k sorted linked lists into one sorted linked list.

    >>> to_list(
    ...     merge_k_sorted(
    ...         [from_list([1, 4, 5]), from_list([1, 3, 4]), from_list([2, 6])]
    ...     )
    ... )
    [1, 1, 2, 3, 4, 4, 5, 6]
    """
    heap: list[tuple[int, int, ListNode]] = []

    for i, node in enumerate(lists):
        if node:
            heap.append((node.val, i, node))

    heapq.heapify(heap)

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _val, idx, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))

    return dummy.next

to_list 

to_list(head: ListNode | None) -> list[int]

Collect linked list values into a Python list.

Source code in src/algo/heaps/merge_k_sorted_lists.py 
74
75
76
77
78
79
80
def to_list(head: ListNode | None) -> list[int]:
    """Collect linked list values into a Python list."""
    result: list[int] = []
    while head:
        result.append(head.val)
        head = head.next
    return result
tests/heaps/test_merge_k_sorted_lists.py
"""Tests for merge k sorted linked lists."""

from algo.heaps.merge_k_sorted_lists import from_list, merge_k_sorted, to_list


class TestMergeKSorted:
    def test_basic(self) -> None:
        lists = [from_list([1, 4, 5]), from_list([1, 3, 4]), from_list([2, 6])]
        assert to_list(merge_k_sorted(lists)) == [1, 1, 2, 3, 4, 4, 5, 6]

    def test_empty_input(self) -> None:
        assert merge_k_sorted([]) is None

    def test_all_empty_lists(self) -> None:
        assert merge_k_sorted([None, None, None]) is None

    def test_single_list(self) -> None:
        assert to_list(merge_k_sorted([from_list([1, 2, 3])])) == [1, 2, 3]

    def test_some_empty_lists(self) -> None:
        lists = [from_list([1, 3]), None, from_list([2, 4])]
        assert to_list(merge_k_sorted(lists)) == [1, 2, 3, 4]

    def test_single_element_lists(self) -> None:
        lists = [from_list([5]), from_list([1]), from_list([3])]
        assert to_list(merge_k_sorted(lists)) == [1, 3, 5]

    def test_negative_values(self) -> None:
        lists = [from_list([-5, -1, 3]), from_list([-3, 0, 2])]
        assert to_list(merge_k_sorted(lists)) == [-5, -3, -1, 0, 2, 3]

Implement it yourself

Run: just challenge heaps merge_k_sorted_lists

Then implement the functions to make all tests pass. Use just study heaps for watch mode.

Reveal Solution

merge_k_sorted_lists

Merge k sorted linked lists.

Problem

Given an array of k sorted linked lists, merge them into one sorted linked list.

Approach

Use a min-heap of size k. Push (value, list_index, node) tuples. Pop the smallest, append to result, and push the next node from that list. The list_index breaks ties to avoid comparing nodes.

When to use

K-way merge for external sorting — "merge K sorted lists/arrays/files", combining sorted partitions from distributed systems. Min-heap of size k selects the next smallest element. See also: merge_two_sorted.

Complexity

Time: O(n log k) where n = total nodes across all lists Space: O(k) for the heap

from_list 

from_list(vals: list[int]) -> ListNode | None

Build a linked list from a Python list.

Source code in src/algo/heaps/merge_k_sorted_lists.py 
64
65
66
67
68
69
70
71
def from_list(vals: list[int]) -> ListNode | None:
    """Build a linked list from a Python list."""
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next

merge_k_sorted 

merge_k_sorted(
    lists: list[ListNode | None],
) -> ListNode | None

Merge k sorted linked lists into one sorted linked list.

to_list( ... merge_k_sorted( ... [from_list([1, 4, 5]), from_list([1, 3, 4]), from_list([2, 6])] ... ) ... ) [1, 1, 2, 3, 4, 4, 5, 6]

Source code in src/algo/heaps/merge_k_sorted_lists.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def merge_k_sorted(lists: list[ListNode | None]) -> ListNode | None:
    """Merge k sorted linked lists into one sorted linked list.

    >>> to_list(
    ...     merge_k_sorted(
    ...         [from_list([1, 4, 5]), from_list([1, 3, 4]), from_list([2, 6])]
    ...     )
    ... )
    [1, 1, 2, 3, 4, 4, 5, 6]
    """
    heap: list[tuple[int, int, ListNode]] = []

    for i, node in enumerate(lists):
        if node:
            heap.append((node.val, i, node))

    heapq.heapify(heap)

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _val, idx, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))

    return dummy.next

to_list 

to_list(head: ListNode | None) -> list[int]

Collect linked list values into a Python list.

Source code in src/algo/heaps/merge_k_sorted_lists.py 
74
75
76
77
78
79
80
def to_list(head: ListNode | None) -> list[int]:
    """Collect linked list values into a Python list."""
    result: list[int] = []
    while head:
        result.append(head.val)
        head = head.next
    return result