Reverse Linked List

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

Examples

• 0 ≤ length of list ≤ 1000
• -1000 ≤ Node.val ≤ 1000

Prerequisites

• Linked List Fundamentals — understanding the node structure with val and next, and basic traversal
• Pointer Manipulation — redirecting next pointers without losing references to the rest of the list
• Recursion Basics — understanding how the call stack unwinds for the recursive approach

1. Recursion

Intuition

Think of it as: “reverse everything after me, then make my right neighbor point back at me.” When we recurse all the way to the last node, it becomes the new head. As the call stack unwinds, each node uses head.next.next = head to reverse its connection, then sets head.next = None to cut the old forward link.

The key insight is that head.next still points to the node immediately after head even after the recursive call has reversed the sublist — so we can use it to make that node point back to head.

Algorithm

• Base case: if head is None or has no next, return head.
• Recursively reverse head.next. This returns newHead — the new front of the reversed sublist.
• Set head.next.next = head — make the node after head point back at head.
• Set head.next = None — break the old forward link (otherwise a cycle forms).
• Return newHead.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head
        head.next = None

        return newHead

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Time Complexity: O(n)
Space Complexity: O(n) — call stack depth equals list length.

2. Iteration

Intuition

Walk through the list left to right. At each node, flip its next pointer to point backward instead of forward. Three pointers do all the work:

• curr — the node we're currently processing
• prev — the node that curr should point to after reversal (starts as None)
• temp — saved reference to curr.next before we overwrite it

Without saving temp = curr.next first, we'd lose the reference to the rest of the list the moment we do curr.next = prev. After the pointer flip, we advance both prev and curr one step forward (using the saved temp). When curr reaches None, prev is sitting on the new head.

Algorithm

• Initialize prev = None, curr = head.
• While curr is not None:
• Save — temp = curr.next
• Flip — curr.next = prev
• Advance prev — prev = curr
• Advance curr — curr = temp
• Return prev — the new head.

Common Pitfalls

Losing the Next Node Before Saving It

The most common mistake is writing curr.next = prev before saving temp = curr.next. Once you overwrite curr.next, you permanently lose the reference to the rest of the list. Always save first.

# Wrong: loses the rest of the list
curr.next = prev          # ← overwrites before saving
temp = curr.next          # ← now temp = prev, not the next node!

# Correct: save first, then flip
temp = curr.next          # ← save next node
curr.next = prev          # ← now safe to flip

Forgetting to Set the Original Head's Next to None (Recursion)

In the recursive approach, after head.next.next = head is set, head.next still points forward — creating a cycle between head and the node after it. Setting head.next = None breaks that cycle and correctly makes head the new tail.

Returning curr Instead of prev

At the end of the iterative loop, curr is None (one step past the last node). The new head is prev, which is sitting on the last original node. Returning curr returns None — an empty list.