LeetCode 206 - Reverse Linked List

2026-07-08

easy　linked list　recursion

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

Example 1:

Input: head = [0,1,2,3]

Output: [3,2,1,0]

Example 2:

Input: head = []

Output: []

Constraints:

• 0 <= list length <= 1,000
• -1,000 <= Node.val <= 1,000

Solution 1:

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

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Approach: Iterative — Three-Pointer Reversal
        # The core challenge: redirecting cur.next to prev disconnects cur from the rest
        # of the list, so we must save the original next pointer before overwriting it.
        #
        # Three pointers:
        #   cur  — the node currently being reversed.
        #   prev — the head of the already-reversed portion (starts as None).
        #   tmp  — saves cur.next before we overwrite it.
        #
        # Each iteration:
        # 1. Save cur.next in tmp so we don't lose the rest of the list.
        # 2. Point cur.next backward to prev (the reversal step).
        # 3. Advance prev to cur, and cur to tmp.
        # When cur reaches None, prev is the new head of the fully reversed list.
        # Time Complexity: O(N).
        # Space Complexity: O(1).
        cur = head
        prev = None

        while cur:
            tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp

        return prev

Solution 2:

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

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Approach: Recursive
        # Recurse all the way to the tail, then reverse the links on the way back up.
        #
        # Walk-through with [1 -> 2 -> 3 -> None]:
        # - Recurse until node 3 (no next) — base case returns 3 as new_head.
        # - Back at node 2: head.next is 3, so head.next.next = head makes 3 point to 2.
        #   Then head.next = None severs 2's original forward link.
        # - Back at node 1: head.next is 2, so head.next.next = head makes 2 point to 1.
        #   Then head.next = None severs 1's original forward link.
        # - new_head (node 3) bubbles up unchanged through every frame.
        # Time Complexity: O(N) — one call per node.
        # Space Complexity: O(N) — recursion stack depth equals the list length.
        if not head or not head.next:
            return head

        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return new_head

Conclusion

Today we reversed a linked list two ways.

The iterative solution is the standard answer — three pointers, one pass, O(1) space. The key detail is saving cur.next into tmp before overwriting cur.next = prev. Without that save, we lose the rest of the list the moment we redirect the pointer.

The recursive solution reverses on the way back up the call stack. It recurses to the tail first, then as each frame returns, it wires head.next.next = head (make the next node point back) and head.next = None (cut the original forward link). The new head from the base case propagates back up unchanged through every frame.

Both run in O(N) time. The iterative version uses O(1) space; the recursive version uses O(N) stack space. For interviews, the iterative approach is usually preferred — but being able to explain both demonstrates a solid understanding of how linked list manipulation works.