Merge Two Sorted

Problem

Given the heads of two sorted linked lists, merge them into one sorted list built from the nodes of the two input lists.

Approach

Use a dummy head node and compare the fronts of both lists, advancing the smaller one each time.

When to Use

Merge step of merge sort — combining two sorted sequences into one. Building block for merge_k_sorted_lists and external merge sort. Keywords: "merge sorted", "interleave ordered streams".

Complexity

Time	O(n + m)
Space	O(1) — only pointer manipulation, no new nodes allocated

Implementation

SolutionTestsChallenge

merge_two_sorted

Merge two sorted linked lists.

Problem

Given the heads of two sorted linked lists, merge them into one sorted list built from the nodes of the two input lists.

Approach

Use a dummy head node and compare the fronts of both lists, advancing the smaller one each time.

When to use

Merge step of merge sort — combining two sorted sequences into one. Building block for merge_k_sorted_lists and external merge sort. Keywords: "merge sorted", "interleave ordered streams".

Complexity

Time: O(n + m) Space: O(1) — only pointer manipulation, no new nodes allocated

from_list

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

Build a linked list from a Python list.

Source code in src/algo/linked_lists/merge_two_sorted.py

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_two_sorted

merge_two_sorted(
    l1: ListNode | None, l2: ListNode | None
) -> ListNode | None

Merge two sorted linked lists into one sorted list.

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

Source code in src/algo/linked_lists/merge_two_sorted.py

def merge_two_sorted(
    l1: ListNode | None,
    l2: ListNode | None,
) -> ListNode | None:
    """Merge two sorted linked lists into one sorted list.

    >>> to_list(merge_two_sorted(from_list([1, 3, 5]), from_list([2, 4, 6])))
    [1, 2, 3, 4, 5, 6]
    """
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    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/linked_lists/merge_two_sorted.py

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/linked_lists/test_merge_two_sorted.py

"""Tests for merge two sorted linked lists."""

from hypothesis import given
from hypothesis import strategies as st

from algo.linked_lists.merge_two_sorted import from_list, merge_two_sorted, to_list


class TestMergeTwoSorted:
    def test_basic(self) -> None:
        result = merge_two_sorted(from_list([1, 3, 5]), from_list([2, 4, 6]))
        assert to_list(result) == [1, 2, 3, 4, 5, 6]

    def test_overlapping_values(self) -> None:
        result = merge_two_sorted(from_list([1, 2, 4]), from_list([1, 3, 4]))
        assert to_list(result) == [1, 1, 2, 3, 4, 4]

    def test_first_empty(self) -> None:
        result = merge_two_sorted(None, from_list([1, 2, 3]))
        assert to_list(result) == [1, 2, 3]

    def test_second_empty(self) -> None:
        result = merge_two_sorted(from_list([1, 2, 3]), None)
        assert to_list(result) == [1, 2, 3]

    def test_both_empty(self) -> None:
        assert merge_two_sorted(None, None) is None

    def test_single_elements(self) -> None:
        result = merge_two_sorted(from_list([2]), from_list([1]))
        assert to_list(result) == [1, 2]

    @given(
        a=st.lists(st.integers(min_value=-100, max_value=100), min_size=0, max_size=30),
        b=st.lists(st.integers(min_value=-100, max_value=100), min_size=0, max_size=30),
    )
    def test_result_is_sorted(self, a: list[int], b: list[int]) -> None:
        a.sort()
        b.sort()
        result = to_list(merge_two_sorted(from_list(a), from_list(b)))
        assert result == sorted(a + b)

Implement it yourself

Run: just challenge linked_lists merge_two_sorted

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

Reveal Solution

merge_two_sorted

Merge two sorted linked lists.

Problem

Given the heads of two sorted linked lists, merge them into one sorted list built from the nodes of the two input lists.

Approach

Use a dummy head node and compare the fronts of both lists, advancing the smaller one each time.

When to use

Merge step of merge sort — combining two sorted sequences into one. Building block for merge_k_sorted_lists and external merge sort. Keywords: "merge sorted", "interleave ordered streams".

Complexity

Time: O(n + m) Space: O(1) — only pointer manipulation, no new nodes allocated

from_list

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

Build a linked list from a Python list.

Source code in src/algo/linked_lists/merge_two_sorted.py

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_two_sorted

merge_two_sorted(
    l1: ListNode | None, l2: ListNode | None
) -> ListNode | None

Merge two sorted linked lists into one sorted list.

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

Source code in src/algo/linked_lists/merge_two_sorted.py

def merge_two_sorted(
    l1: ListNode | None,
    l2: ListNode | None,
) -> ListNode | None:
    """Merge two sorted linked lists into one sorted list.

    >>> to_list(merge_two_sorted(from_list([1, 3, 5]), from_list([2, 4, 6])))
    [1, 2, 3, 4, 5, 6]
    """
    dummy = ListNode(0)
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    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/linked_lists/merge_two_sorted.py

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