Reverse Linked List | Leetcode 206 | Iterative vs Recursive Solution

The “Reverse Linked List” problem is one of the most fundamental and frequently asked problems in data structures. It tests your understanding of pointer manipulation and recursion in a singly linked list.

In this blog, we’ll walk through three detailed approaches: brute force, iterative, and recursive. We’ll explain the intuition, approach, and provide an easy-to-understand code explanation for each method.

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

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: Brute Force Approach (Using Stack)

Intuition

Think of this like stacking plates! When you put plates on a stack, the last plate you put becomes the first one you take out. We’ll use this same idea – store all the values in a stack, then put them back in reverse order.

Detailed Approach

1. First Pass: Walk through the entire linked list and store all node values in a stack
2. Second Pass: Walk through the linked list again and replace each node’s value with values popped from the stack
3. Since stack follows LIFO (Last In, First Out), we get the reverse order automatically

Code

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        temp = head
        stack = []
        
        # First pass: Store all values in stack
        while temp is not None:
            stack.append(temp.val)  # Push current node's value to stack
            temp = temp.next
        
        temp = head  # Reset temp to head for second pass
        
        # Second pass: Pop values from stack and update nodes
        while temp is not None:
            temp.val = stack.pop()  # Replace current value with stack's top
            temp = temp.next
        
        return head

Code Explanation

We use two separate loops here. In the first loop, we visit every node and push its value onto our stack. This gives us all values stored in reverse order (since stack is LIFO). In the second loop, we visit each node again but this time we pop values from the stack and update each node’s value. Since we’re popping in reverse order, we effectively reverse the entire list.

Dry Run

Let’s trace through: 1 -> 2 -> 3

First Pass:

• Visit node 1: stack = 
• Visit node 2: stack = 
• Visit node 3: stack = 

Second Pass:

• Visit node 1: pop 3, node becomes 3: 3 -> 2 -> 3
• Visit node 2: pop 2, node becomes 2: 3 -> 2 -> 3
• Visit node 3: pop 1, node becomes 1: 3 -> 2 -> 1

Result: 3 -> 2 -> 1

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list twice
• Space Complexity: O(n) – We store all values in the stack

Simplifying It

This approach is easy to understand but uses extra space. We’re basically copying all values to a temporary storage (stack) and then putting them back in reverse order.

Solution 2: Iterative Approach (Optimal)

Intuition

Imagine you’re holding hands in a line and want to face the opposite direction. Instead of everyone turning around, you can change who’s holding whose hand! Each person just needs to hold the hand of the person who was previously behind them.

Detailed Approach

1. Track Three Pointers: Keep track of previous node, current node, and next node
2. Reverse the Link: Make current node point to the previous node instead of the next node
3. Move Forward: Shift all pointers one step forward
4. Repeat: Continue until we reach the end of the list

Code

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        temp = head    # Current node we're processing
        prev = None    # Previous node (starts as None)
        
        while temp is not None:
            front = temp.next     # Store next node before we lose it
            temp.next = prev      # Reverse the link: point to previous
            prev = temp           # Move prev pointer forward
            temp = front          # Move current pointer forward
        
        return prev  # prev is now the new head of reversed list

Code Explanation

We use three pointers to carefully reverse each link. The front pointer helps us remember where to go next before we break the current connection. We reverse each arrow one by one, making sure not to lose track of where we are in the list. By the end, prev points to what used to be the last node, which is now our new first node.

Dry Run

Let’s trace through: 1 -> 2 -> 3

Initial: temp=1, prev=None

None <- 1 -> 2 -> 3
       ^    ^
     prev  temp

Step 1: front=2, reverse link, move pointers

None <- 1    2 -> 3
            ^    ^
          prev  temp

Step 2: front=3, reverse link, move pointers

None <- 1 <- 2    3
                 ^    ^
               prev  temp

Step 3: front=None, reverse link, move pointers

None <- 1 <- 2 <- 3    None
                  ^      ^
                prev   temp

Result: Return prev (which points to 3)

Time and Space Complexity

• Time Complexity: O(n) – We visit each node exactly once
• Space Complexity: O(1) – We only use a few pointer variables

Simplifying It

This is the most efficient approach! We change the direction of arrows one by one without needing any extra storage space. Just like redirecting traffic flow on a one-way street.

Solution 3: Recursive Approach

Intuition

Think of this like a chain of people passing a message backwards. Each person tells the person behind them to reverse their part of the chain, then fixes their own connection. It’s like solving smaller versions of the same problem.

Detailed Approach

1. Base Case: If we reach the end (or empty list), stop the recursion
2. Recursive Call: Ask the rest of the list to reverse itself
3. Fix Current Connection: Once the rest is reversed, fix the current node’s connection
4. Return New Head: The deepest recursive call found the new head, keep passing it back

Code

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Base case: empty list or single node
        if head is None or head.next is None:
            return head
        
        # Recursively reverse the rest of the list
        new_head = self.reverseList(head.next)
        
        # Fix the current connection
        front = head.next          # The node that comes after current
        front.next = head          # Make it point back to current
        head.next = None           # Remove current's forward connection
        
        return new_head  # Return the head of the reversed list

Code Explanation

The recursion goes deep until it finds the last node, which becomes the new head. As the recursive calls return, each level fixes its own connection by making the next node point backwards. It’s like a domino effect in reverse – each piece fixes its connection as the solution bubbles back up.

Dry Run

Let’s trace through: 1 -> 2 -> 3

Call Stack:

reverseList(1): calls reverseList(2)
  reverseList(2): calls reverseList(3)
    reverseList(3): returns 3 (base case)
  reverseList(2): new_head=3, fix 3->2, return 3
reverseList(1): new_head=3, fix 2->1, return 3

Step by step:

1. reverseList(3) returns 3 (base case)
2. reverseList(2) gets new_head=3, makes 3 point to 2: 1 -> 2 <- 3
3. reverseList(1) gets new_head=3, makes 2 point to 1: None <- 1 <- 2 <- 3

Result: Returns 3 as the new head

Time and Space Complexity

• Time Complexity: O(n) – We visit each node exactly once
• Space Complexity: O(n) – Due to recursion call stack (n recursive calls)

Simplifying It

This approach is elegant but uses extra memory for the call stack. Each recursive call waits for the next one to finish, like a stack of function calls. It’s beautiful conceptually but not the most memory-efficient for large lists.

Summary

The iterative approach is typically the best choice as it’s efficient in both time and space. However, understanding all three approaches helps you tackle similar problems with different constraints!