Reverse Linked List

Problem

Given the head of a singly linked list, reverse the list and return the new head.

Approach

Iterative: Walk the list with prev/curr pointers, reversing each link. Recursive: Reverse the rest of the list, then point the next node back.

When to Use

In-place linked list reversal — "reverse list", "reverse sublist", pointer manipulation without extra space. Building block for palindrome check, k-group reversal, and reorder-list problems.

Complexity

Time	O(n)
Space	O(1) iterative, O(n) recursive (call stack)

Implementation

SolutionTestsChallenge

reverse_linked_list

Reverse a singly linked list.

Problem

Given the head of a singly linked list, reverse the list and return the new head.

Approach

Iterative: Walk the list with prev/curr pointers, reversing each link. Recursive: Reverse the rest of the list, then point the next node back.

When to use

In-place linked list reversal — "reverse list", "reverse sublist", pointer manipulation without extra space. Building block for palindrome check, k-group reversal, and reorder-list problems.

Complexity

Time: O(n) Space: O(1) iterative, O(n) recursive (call stack)

from_list

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

Build a linked list from a Python list.

Source code in src/algo/linked_lists/reverse_linked_list.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

reverse_iterative

reverse_iterative(head: ListNode | None) -> ListNode | None

Reverse a linked list in place using iteration.

to_list(reverse_iterative(from_list([1, 2, 3]))) [3, 2, 1]

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

def reverse_iterative(head: ListNode | None) -> ListNode | None:
    """Reverse a linked list in place using iteration.

    >>> to_list(reverse_iterative(from_list([1, 2, 3])))
    [3, 2, 1]
    """
    prev: ListNode | None = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

reverse_recursive

reverse_recursive(head: ListNode | None) -> ListNode | None

Reverse a linked list using recursion.

to_list(reverse_recursive(from_list([1, 2, 3]))) [3, 2, 1]

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

def reverse_recursive(head: ListNode | None) -> ListNode | None:
    """Reverse a linked list using recursion.

    >>> to_list(reverse_recursive(from_list([1, 2, 3])))
    [3, 2, 1]
    """
    if not head or not head.next:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

to_list

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

Collect linked list values into a Python list.

Source code in src/algo/linked_lists/reverse_linked_list.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_reverse_linked_list.py

"""Tests for reverse linked list."""

from hypothesis import given
from hypothesis import strategies as st

from algo.linked_lists.reverse_linked_list import (
    from_list,
    reverse_iterative,
    reverse_recursive,
    to_list,
)


class TestReverseIterative:
    def test_basic(self) -> None:
        assert to_list(reverse_iterative(from_list([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]

    def test_single_node(self) -> None:
        assert to_list(reverse_iterative(from_list([42]))) == [42]

    def test_two_nodes(self) -> None:
        assert to_list(reverse_iterative(from_list([1, 2]))) == [2, 1]

    def test_empty_list(self) -> None:
        assert reverse_iterative(None) is None

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

    @given(
        data=st.lists(
            st.integers(min_value=-1000, max_value=1000), min_size=1, max_size=50
        )
    )
    def test_double_reverse_is_identity(self, data: list[int]) -> None:
        head = from_list(data)
        assert to_list(reverse_iterative(reverse_iterative(head))) == data


class TestReverseRecursive:
    def test_basic(self) -> None:
        assert to_list(reverse_recursive(from_list([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]

    def test_single_node(self) -> None:
        assert to_list(reverse_recursive(from_list([42]))) == [42]

    def test_two_nodes(self) -> None:
        assert to_list(reverse_recursive(from_list([1, 2]))) == [2, 1]

    def test_empty_list(self) -> None:
        assert reverse_recursive(None) is None

    @given(
        data=st.lists(
            st.integers(min_value=-1000, max_value=1000), min_size=1, max_size=50
        )
    )
    def test_matches_iterative(self, data: list[int]) -> None:
        assert to_list(reverse_recursive(from_list(data))) == to_list(
            reverse_iterative(from_list(data))
        )

Implement it yourself

Run: just challenge linked_lists reverse_linked_list

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

Reveal Solution

reverse_linked_list

Reverse a singly linked list.

Problem

Given the head of a singly linked list, reverse the list and return the new head.

Approach

Iterative: Walk the list with prev/curr pointers, reversing each link. Recursive: Reverse the rest of the list, then point the next node back.

When to use

In-place linked list reversal — "reverse list", "reverse sublist", pointer manipulation without extra space. Building block for palindrome check, k-group reversal, and reorder-list problems.

Complexity

Time: O(n) Space: O(1) iterative, O(n) recursive (call stack)

from_list

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

Build a linked list from a Python list.

Source code in src/algo/linked_lists/reverse_linked_list.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

reverse_iterative

reverse_iterative(head: ListNode | None) -> ListNode | None

Reverse a linked list in place using iteration.

to_list(reverse_iterative(from_list([1, 2, 3]))) [3, 2, 1]

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

def reverse_iterative(head: ListNode | None) -> ListNode | None:
    """Reverse a linked list in place using iteration.

    >>> to_list(reverse_iterative(from_list([1, 2, 3])))
    [3, 2, 1]
    """
    prev: ListNode | None = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

reverse_recursive

reverse_recursive(head: ListNode | None) -> ListNode | None

Reverse a linked list using recursion.

to_list(reverse_recursive(from_list([1, 2, 3]))) [3, 2, 1]

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

def reverse_recursive(head: ListNode | None) -> ListNode | None:
    """Reverse a linked list using recursion.

    >>> to_list(reverse_recursive(from_list([1, 2, 3])))
    [3, 2, 1]
    """
    if not head or not head.next:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

to_list

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

Collect linked list values into a Python list.

Source code in src/algo/linked_lists/reverse_linked_list.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