206. Reverse Linked List

Reformulated question¶

Reverse a singly linked list in-place and return the new head.

Example:

head: 1 -> 2 -> 3 -> None
return: 3 -> 2 -> 1 -> None

Key trick¶

Keep 3 pointers while scanning once:

prev = already reversed part
cur = current node
nxt = saved next node before rewiring

The key is to save cur.next before changing it.

Trap¶

Common mistakes:

Losing the rest of the list by doing cur.next = prev before saving the original next node
Returning the old head instead of the new head prev
Reusing the same mutated linked list in multiple tests
Recursive solution may hit recursion limits in Python on larger inputs

Why is this question interesting?¶

It tests pointer manipulation, in-place mutation, and whether you can reason about linked structure without extra memory.

Solve the problem with idiomatic python¶

class SolutionIterative:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # prev is the reversed prefix, head walks the unreversed suffix
        prev = None
        cur = head

        while cur:
            nxt = cur.next      # save tail before rewiring
            cur.next = prev     # reverse pointer
            prev = cur          # grow reversed prefix
            cur = nxt           # continue forward

        return prev

class SolutionRecursive:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def dfs(cur: Optional[ListNode], prev: Optional[ListNode]) -> Optional[ListNode]:
            if cur is None:
                return prev
            nxt = cur.next
            cur.next = prev
            return dfs(nxt, cur)

        return dfs(head, None)

Pytest test¶

@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([], []),
        ([1], [1]),
        ([1, 2], [2, 1]),
        ([1, 2, 3, 4, 5], [5, 4, 3, 2, 1]),
        ([0, -1, 3], [3, -1, 0]),
    ],
)
def test_reverse_list(values, expected):
    head1 = build_linked_list(values)
    head2 = build_linked_list(values)

    assert linked_list_to_list(SolutionIterative().reverseList(head1)) == expected
    assert linked_list_to_list(SolutionRecursive().reverseList(head2)) == expected

Comment my solution¶

Your solution is correct and clean.

Good points:

Iterative version uses the standard \(O(n)\) time, \(O(1)\) extra space approach
Recursive version is also correct and mirrors the same state transition well
Test correctly rebuilds the list twice, which avoids mutation issues

Small improvements:

In SolutionIterative, names like cur and prev are more standard than tail and reversed_list
In SolutionRecursive, reverse could be a nested helper since it is not useful outside reverseList
Add a one-element test case like [1]

from typing import Optional
import pytest

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return f"ListNode({self.val})"


def build_linked_list(values):
    dummy = ListNode()
    cur = dummy
    for v in values:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


def linked_list_to_list(head):
    out = []
    cur = head
    while cur:
        out.append(cur.val)
        cur = cur.next
    return out


class SolutionIterative:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        tail = head
        reversed_list = None
        while tail:
            head = tail
            tail = tail.next
            head.next = reversed_list
            reversed_list = head
        return reversed_list


class SolutionRecursive:
    def reverse(self, head, reversed_list):
        if head is None:
            return reversed_list
        new_head = head.next
        head.next = reversed_list
        return self.reverse(new_head, head)

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.reverse(head, None)

@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([1, 2, 3, 4, 5], [5, 4, 3, 2, 1]),
        ([1, 2], [2, 1]),
        ([], [])
    ]
)
def test_reverseList(values, expected):
    head_rec = build_linked_list(values)
    head_iter = build_linked_list(values)
    reversed_list_recursive = SolutionRecursive().reverseList(head_rec)
    reversed_list_iterative = SolutionIterative().reverseList(head_iter)
    assert linked_list_to_list(reversed_list_recursive) == expected
    assert linked_list_to_list(reversed_list_iterative) == expected

Code¶

from typing import Optional
import pytest


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return f"ListNode({self.val})"


def build_linked_list(values):
    dummy = ListNode()
    cur = dummy
    for v in values:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


def linked_list_to_list(head):
    out = []
    cur = head
    while cur:
        out.append(cur.val)
        cur = cur.next
    return out


class SolutionIterative:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # prev is the reversed prefix, cur is the remaining suffix
        prev = None
        cur = head

        while cur:
            nxt = cur.next      # save next before changing links
            cur.next = prev     # reverse current pointer
            prev = cur          # advance reversed prefix
            cur = nxt           # move forward

        return prev


class SolutionRecursive:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Same state as iterative: (cur, prev)
        def dfs(cur: Optional[ListNode], prev: Optional[ListNode]) -> Optional[ListNode]:
            if cur is None:
                return prev
            nxt = cur.next
            cur.next = prev
            return dfs(nxt, cur)

        return dfs(head, None)


@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([], []),
        ([1], [1]),
        ([1, 2], [2, 1]),
        ([1, 2, 3, 4, 5], [5, 4, 3, 2, 1]),
        ([0, -1, 3], [3, -1, 0]),
    ],
)
def test_reverse_list(values, expected):
    head1 = build_linked_list(values)
    head2 = build_linked_list(values)

    assert linked_list_to_list(SolutionIterative().reverseList(head1)) == expected
    assert linked_list_to_list(SolutionRecursive().reverseList(head2)) == expected


linked_list_to_list(SolutionIterative().reverseList(build_linked_list([1, 2, 3])))
linked_list_to_list(SolutionRecursive().reverseList(build_linked_list([1, 2, 3])))