Skip to content

206. Reverse Linked List

On LeetCode ->

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

from typing import Optional
from utils import ListNode

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

from typing import Optional
from utils import ListNode

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

from utils import list_build, list_to_python_list

@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 = list_build(values)
    head2 = list_build(values)

    assert list_to_python_list(SolutionIterative().reverseList(head1)) == expected
    assert list_to_python_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
from utils import ListNode, list_build, list_to_python_list

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 = list_build(values)
    head_iter = list_build(values)
    reversed_list_recursive = SolutionRecursive().reverseList(head_rec)
    reversed_list_iterative = SolutionIterative().reverseList(head_iter)
    assert list_to_python_list(reversed_list_recursive) == expected
    assert list_to_python_list(reversed_list_iterative) == expected