Reverse Linked List

Difficulty: Easy
Topics: Linked List, Recursion
Link: https://leetcode.com/problems/reverse-linked-list/

Problem Description

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

Example 1:


Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:


Input: head = [1,2]
Output: [2,1]

Example 3:


Input: head = []
Output: []

Constraints:

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution

1. Problem Deconstruction

Rewrite the Problem

Technical Definition:
Given the head node of a singly linked list, reverse the direction of all pointers such that each node points to its predecessor instead of its successor. The final node becomes the new head, and the original head becomes the tail (pointing to null). Return the head of the reversed list.
Beginner Explanation:
Imagine a conga line where each person holds the shoulders of the next person. Reversing the list means turning the line around so the last person is now first, and everyone now holds the shoulders of the person behind them in the original line. The task is to reorganize the pointers in this way.
Mathematical Formulation:
Let ( L = (n_1 \rightarrow n_2 \rightarrow \cdots \rightarrow n_k) ) be a linked list where ( \forall i \in [1, k-1]: n_i.\text{next} = n_{i+1} ) and ( n_k.\text{next} = \text{null} ).
Transform ( L ) into ( L’ = (n_k \rightarrow n_{k-1} \rightarrow \cdots \rightarrow n_1) ) such that:
- ( \forall j \in [2, k]: n_j.\text{next} = n_{j-1} )
- ( n_1.\text{next} = \text{null} )
  Return ( n_k ) (head of ( L’ )).

Constraint Analysis

Number of nodes in [0, 5000]:
- Limitation: Requires handling empty lists (0 nodes) and scales to large inputs. O(n) time solutions are acceptable (5000 ops), but O(n²) is borderline (25e6 ops).
- Edge Case: Empty list (head = null) must return null. Single-node lists are invariant under reversal.
Node values in [-5000, 5000]:
- Limitation: Values don’t affect pointer manipulation, but edge cases like val = 0 or negative values must not break logic.
- Hidden Implication: Algorithm must rely solely on pointer rearrangement, not value swapping.

2. Intuition Scaffolding

Analogies

Real-World Metaphor (Domino Train):
Flipping a domino chain: Start from the last domino, redirect each domino to point backward. Requires temporarily storing the next domino before redirection to avoid “chain collapse”.
Gaming Analogy (Treasure Hunt):
Original clues lead forward; reversing is like starting at the treasure and following clues backward. Recursive: Solve smaller hunt (sub-list), then backtrack to update pointers.
Math Analogy (Permutation):
Reversal is a permutation ( \sigma(i) = k - i + 1 ). Iterative: Apply transpositions pairwise. Recursive: Inductively reverse ( k-1 ) elements, then prepend ( n_k ).

Common Pitfalls

Losing Node References:
Overwriting curr.next without saving next_node severs the list.
Incorrect Termination:
New tail (original head) must point to null; otherwise, cycles form.
Edge Case Neglect:
Empty/single-node lists bypass reversal logic.
Recursive Stack Overflow:
5000 nodes may exceed stack limits in some languages.
Partial Reversal:
Stopping early (e.g., at curr.next == null) leaves nodes unprocessed.

3. Approach Encyclopedia

Approach 1: Iterative Reversal

Concept: Traverse list, redirecting each node’s pointer to its predecessor.
Pseudocode:

def reverseList(head):
    prev = None       # Predecessor of current node (starts as null)
    curr = head       # Start traversal at head
    while curr:       # Process all nodes
        next_node = curr.next  # Save next node before overwriting
        curr.next = prev       # Reverse pointer backward
        prev = curr            # Move prev forward
        curr = next_node       # Move curr forward
    return prev       # Last non-null node (new head)

Complexity Proof:

Time: Each node visited exactly once → ( \sum_{i=1}^{n} O(1) = O(n) ).
Space: Three pointers ( O(1) ).

Visualization:

Original: 1 → 2 → 3 → null  
Step 1: prev=null, curr=1 → save next_node=2 → 1→null, prev=1, curr=2  
Step 2: curr=2 → next_node=3 → 2→1, prev=2, curr=3  
Step 3: curr=3 → next_node=null → 3→2, prev=3, curr=null → return 3  
Final: 3 → 2 → 1 → null

Approach 2: Recursive Reversal

Concept: Recursively reverse sublist starting from head.next, then redirect pointers.
Pseudocode:

def reverseList(head):
    if not head or not head.next:  # Base case: 0 or 1 node
        return head
    reversed_head = reverseList(head.next)  # Reverse sublist
    head.next.next = head   # Redirect successor to point back
    head.next = null        # Break original forward link
    return reversed_head    # Head of fully reversed list

Complexity Proof:

Time: ( n ) recursive calls × ( O(1) ) work per call → ( O(n) ).
Space: Recursion depth = ( n ) → ( O(n) ) stack space.

Visualization:

Reverse(1→2→3):  
  Reverse(2→3) → returns 3→2→null after:  
    2.next.next=2 → makes 3→2→? (wait)  
    2.next=null → 3→2→null  
  Now: 1→2 (but 2 points to null)  
  Set 1.next.next=1 → 2→1  
  Set 1.next=null → 3→2→1→null  
  Return 3

4. Code Deep Dive

Iterative Solution

def reverseList(head: ListNode) -> ListNode:
    if not head:  # Edge: Empty list
        return None
    prev = None   # Predecessor starts as null (new tail terminator)
    curr = head   # Initialize traversal
    while curr:   # Traverse entire list
        next_node = curr.next  # Critical: Save next before overwriting
        curr.next = prev       # Reverse link direction
        prev = curr            # Advance prev to current node
        curr = next_node       # Advance curr to saved next node
    return prev   # Last non-null node is new head

Edge Case Handling:

Empty List (Example 3): if not head returns null.
Two Nodes (Example 2):
- Step 1: curr=1 → next_node=2, 1→null, prev=1, curr=2.
- Step 2: curr=2 → next_node=null, 2→1, prev=2, curr=null → return 2.
Performance: Handles 5000 nodes in O(n) time.

Recursive Solution

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:  # Base: 0/1 node lists unchanged
        return head
    reversed_head = reverseList(head.next)  # Recurse on sublist
    # After recursion, head.next is tail of reversed sublist
    head.next.next = head   # Point tail back to current head
    head.next = None        # Current head becomes new tail
    return reversed_head    # Propagate new head upward