206. Reverse Linked List

Easy · solved 2026-10-05 · Open on LeetCode

linked-listrecursion

Time O(n) · Space O(1)

How to get there

Turn each arrow around

1. Find what actually changes. The nodes and their values stay where they are. Only the arrows flip: each next points to the node before it instead of the one after. The first node ends up pointing to None, and the last node becomes the head.

2. Flip [1, 2, 3] by hand and find where one pass gets stuck. At the 1, set 1.next = None, since nothing comes before it. But 1.next was the only way to reach the 2, so the rest of the list is lost. And at the 2, its arrow has to point back to the 1, which a singly linked list can’t reach from the 2.

3. Find what to remember. Two things the flip would otherwise lose: the node just passed, prev, to point back to, and the rest of the list, next_node, saved before the arrow is overwritten.

4. See the list as two parts. At every step the nodes before node form a reversed list headed by prev, and the nodes from node on are still in their original order. Each turn moves one node from the front of the second part to the front of the first.

5. Decide when to stop. When node is None, every node has been moved, and prev is the head of the reversed list.

6. Check the cost. Each node is flipped once: O(n) time, and three pointers: O(1) space.

The reusable recipe: when an in-place update overwrites the only link to what comes next, save that link first. To reverse a chain, carry the node just passed.

Let the two parts order the four lines

Variable	Always means, at the top of the loop
`prev`	the head of the reversed part, or `None` before any node is moved
`node`	the head of the part still in original order, or `None` once every node is moved

Code	What happened	What it keeps true
`prev, node = None, head`	nothing is reversed yet	the reversed part is empty, and the whole list is still in order
`while node:`	a node is left to move	the loop runs once per node
`next_node = node.next`	`node`’s arrow is about to be overwritten	the rest of the list stays reachable
`node.next = prev`	`node` joins the reversed part	it points to the old head of that part
`prev = node`	the reversed part has a new head	`prev` is that head
`node = next_node`	the original part lost its first node	`node` is its new head
`return prev`	`node` is `None`	`prev` heads the whole reversed list

The order is fixed by what each line reads. next_node = node.next must come before node.next = prev, which overwrites it. node.next = prev must come before prev = node, so it still links to the old head. prev = node must come before node = next_node, so it still holds the node just moved.

The method carries over: write down what each pointer means, then order the updates so that no line reads a value an earlier line already overwrote.

Alternatives compared

Approach	Time	Space	How it works
Copy the values onto a stack	O(n)	O(n)	Push every value, then walk the list again and pop them back in.
Recursion, reverse the rest first	O(n)	O(n)	Reverse `head.next` recursively, then hook `head` onto the end: `head.next.next = head`, `head.next = None`.
Recursion, pass the predecessor down (`solution-1-original.py`)	O(n)	O(n)	Each call points its node to the predecessor it was given, `to_be_tail`, and hands the last node back up as the new head.
Three pointers (chosen, `solution-2-iterative.py`)	O(n)	O(1)	Move one node per turn from the original part to the front of the reversed part.

Both recursions keep one call per node on the stack. Python’s default recursion limit is 1,000 calls, and a 5,000-node list, the largest the problem allows, raised RecursionError under that limit when run locally.

solution-1-original.py is the three-pointer loop written as recursion: to_be_tail plays prev, with one call per node where the loop reuses one variable. The second value reverse returns is always the caller’s own to_be_head, so reversed_tail.next = to_be_head points a node to itself, and the line after it overwrites that.

solution-1-original.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        new_head, _ = self.reverse(head, None)

        return new_head

    def reverse(self, to_be_head: ListNode, to_be_tail: ListNode | None) -> tuple[ListNode | None, ListNode | None]:
        reversed_head = to_be_head
        if not to_be_head:
            return None, to_be_tail
        elif to_be_head.next:
            reversed_head, reversed_tail = self.reverse(to_be_head.next, to_be_head)
            reversed_tail.next = to_be_head

        to_be_head.next = to_be_tail

        return reversed_head, to_be_tail

solution-2-iterative.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        prev, node = None, head
        while node:
            next_node = node.next
            node.next = prev
            prev = node
            node = next_node
        return prev

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.