L9: Reverse a Linked List (Iterative and Recursive)

Reversing a linked list is a foundational Data Structures and Algorithms (DSA) interview problem. Given the head of a singly linked list, the objective is to reverse the direction of the pointers so that the tail becomes the new head, and return that new head node.

1. The Problem Statement & The Status Quo

Imagine you are given a singly linked list with nodes containing values such as 1 -> 3 -> 2 -> 5 -> null.

When we reverse this linked list, the physical order of nodes in memory remains intact, but the directional pointers must be inverted:

• Original: 1 -> 3 -> 2 -> 5 -> null
• Reversed: 5 -> 2 -> 3 -> 1 -> null

Our goal is to find and return the new head pointer pointing to 5. Interviewers typically expect candidates to progress from a naive auxiliary space approach to an optimal in-place iterative approach, and finally demonstrate recursive mastery.

2. Naive Approach: Using an External Stack (Two-Pass Solution)

Core Mental Model / Analogy

Real-Life Analogy: Imagine a stack of plates on a table. If you pick them up one by one and place them onto a new pile, the last plate you picked up (the top of the stack) becomes the first plate you can lay down on the new table, naturally reversing their order.

How It Works

1. Pass 1 (Traversal & Storing): Start at the head of the linked list using a temporary pointer (temp). Traverse the entire list node by node, extracting each node's data and pushing it onto an external Stack data structure (std::stack).
2. Pass 2 (Overwriting Data): Reassign temp back to the head of the linked list. Traverse the list a second time. At each node, pop the top element from the stack (stack.top()), overwrite the current node's data with that popped value, and move temp to temp.next.

Code Implementation (C++ / Java Concept)

// Naive Stack-based Reversal (C++)
Node* reverseLinkedListNaive(Node* head) {
    if (head == nullptr || head->next == nullptr) return head;
    
    std::stack<int> st;
    Node* temp = head;
    
    // Pass 1: Push all node data into the stack
    while (temp != nullptr) {
        st.push(temp->data);
        temp = temp->next;
    }
    
    // Pass 2: Pop from stack and overwrite node data
    temp = head;
    while (temp != nullptr) {
        temp->data = st.top();
        st.pop();
        temp = temp->next;
    }
    
    return head;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(2N) \approx \mathcal{O}(N)$, as we traverse the linked list completely twice.
• Space Complexity: $\mathcal{O}(N)$, because we allocate an external stack data structure to store all $N$ integer data values.

Note: Interviewers are typically unsatisfied with this solution because it only reverses the data values inside the nodes rather than the actual pointer links, and it wastes $\mathcal{O}(N)$ extra auxiliary space.

3. The Optimal Iterative Approach (Pointer Reversal)

To optimize space down to $\mathcal{O}(1)$, we cannot use external data structures. We must manipulate the pointer links directly in-place.

Step-by-Step Evolution of Pointers

Instead of moving forward blindly, we need three pointers to safely reverse pointers without losing track of the rest of the list:

1. previous: Tracks the node behind temp. Initially set to null because the old head will become the new tail.
2. temporary (temp): Tracks our current working node during traversal. Initially set to head.
3. front: A temporary look-ahead pointer (temp->next) to ensure we don't lose the rest of the unvisited linked list when we break the forward link.

Vertical Workflow: Pointer Transformation

When we reverse the link, temp->next is pointed to previous. Then, we slide previous and temp forward:

Complete Iterative Code (C++ & Java)

// Optimal Iterative Reversal (C++)
Node* reverseListIterative(Node* head) {
    Node* previous = nullptr;
    Node* temp = head;
    
    while (temp != nullptr) {
        Node* front = temp->next; // 1. Store the next node
        temp->next = previous;    // 2. Reverse the pointer backward
        previous = temp;          // 3. Shift previous forward
        temp = front;             // 4. Shift temp forward
    }
    
    return previous; // 'previous' is now the new head of the reversed list
}

// Optimal Iterative Reversal (Java)
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode temp = head;
        
        while (temp != nullptr || temp != null) { // Note: standard Java syntax uses null
            ListNode front = temp.next;
            temp.next = previous;
            previous = temp;
            temp = front;
        }
        return previous;
    }
}

4. The Recursive Approach: Mental Model & Design

Recursion allows us to break a massive problem down into smaller sub-problems.

Core Mental Model

• The Bigger Problem: Reverse a linked list of size $N$ (e.g., nodes 1 -> 3 -> 2 -> 5 -> null).
• The Sub-problem: Assume our recursive function reverseList(head->next) successfully reverses everything after the head node.
• The Magic Step: Once the sub-list is reversed, our current head node is still pointing forward to its neighbor, but that neighbor now needs to point back to head, and head->next must be set to null.

Base Case

If the linked list is empty (head == null) or has only a single node (head->next == null), it is already reversed. Return head immediately.

5. Recursive Step-by-Step Flow Walkthrough

Let's trace what happens with a 4-node list: 1 -> 3 -> 2 -> 5 -> null.

1. Call 1: reverseList(1) calls reverseList(3).
2. Call 2: reverseList(3) calls reverseList(2).
3. Call 3: reverseList(2) calls reverseList(5).
4. Base Case Hit: reverseList(5) sees 5->next == null, so it returns 5 (the new head).
5. Unwinding & Reversing Links:
   • Back in reverseList(2): head is 2. Its next node 5 (front = head->next) needs to point back to 2: front->next = head (5->next = 2). Then head->next = null (2->next = null). Returns new head 5.
   • Back in reverseList(3): head is 3. Node 2 points to 3, and 3->next = null. Returns new head 5.
   • Back in reverseList(1): head is 1. Node 3 points to 1, and 1->next = null. Returns new head 5.

Complete Recursive Code (C++ & Java)

// Optimal Recursive Reversal (C++)
Node* reverseListRecursive(Node* head) {
    // Base case: empty list or single node
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    
    // Recursive call for the rest of the list
    Node* newHead = reverseListRecursive(head->next);
    
    // Adjust pointers during unwinding
    Node* front = head->next;
    front->next = head;
    head->next = nullptr;
    
    return newHead;
}

// Optimal Recursive Reversal (Java)
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode newHead = reverseList(head.next);
        
        ListNode front = head.next;
        front.next = head;
        head.next = null;
        
        return newHead;
    }
}

6. Comprehensive Strategy Synthesis

7. Summary and Key Takeaways

• Pointer Manipulation is Key: Optimal linked list reversals require modifying .next reference pointers rather than shifting primitive data values.
• The 3-Pointer Technique: In the iterative solution, always maintain a previous pointer, a temp runner, and a front safety keeper to prevent memory leaks or dangling pointers.
• Null Initialization: The previous pointer must start at nullptr (null), because the original head node will become the new tail and must point to null at the end of the list.
• Recursive Unwinding: In recursion, the base case handles the tail node (which becomes the new head), and pointer reversal occurs after the recursive call returns during the stack unwinding phase.
• Space Complexity Tradeoff: While iterative solutions achieve $\mathcal{O}(1)$ auxiliary space, recursive implementations consume $\mathcal{O}(N)$ stack memory due to function call frames.