Reverse a Linked List: Iterative (prev/curr/next) and Recursive

• Iterative reversal – walk the list with three references (prev, curr, next), rewiring each node's link to point backward, in O(n) time and O(1) space.
• Recursive reversal – reverse from the tail: recurse on head.next, then set head.next.next = head and head.next = null, in O(n) time and O(n) stack space.
• Save next – always save curr.next before overwriting it; otherwise the rest of the list is lost.
• New head – after iterative reversal, prev is the new head; after recursive reversal, the base case returns the new head.

What is the problem?

Reverse a singly linked list so that the last node becomes the new head and every next pointer points backward. For example, 1 -> 2 -> 3 becomes 3 -> 2 -> 1.

At the National Bank of India, the statement service stores transactions oldest first but the view shows newest first.

How does the iterative approach work?

Use three pointers: prev (starts at null), curr (starts at head), and next (saved before flipping).

package com.bank.service;

public class ReverseLinkedList {
    public static ListNode reverseIterative(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;  // save the rest
            curr.next = prev;            // flip the link
            prev = curr;                 // advance prev
            curr = next;                 // advance curr
        }
        return prev; // new head
    }

    public static void main(String[] args) {
        // Build: 100 -> 200 -> 300
        ListNode head = new ListNode(100,
            new ListNode(200, new ListNode(300)));
        ListNode reversed = reverseIterative(head);
        // Print: 300 -> 200 -> 100
        ListNode curr = reversed;
        while (curr != null) {
            System.out.print(curr.val + (curr.next != null ? " -> " : "\n"));
            curr = curr.next;
        }
    }
}

300 -> 200 -> 100

Why is saving next essential?

The moment you overwrite curr.next = prev, the forward link to the rest of the list is gone. If you had not saved it, every node after curr becomes unreachable.

// Wrong: rest of list is lost
curr.next = prev;        // link to next nodes is gone!
curr = curr.next;        // curr is now prev, not the original next

// Correct: save first
ListNode next = curr.next;
curr.next = prev;
curr = next;             // curr moves to the saved next

How does the recursive approach work?

Reverse from the tail. If the list is empty or has one node, return it. Otherwise, recurse on head.next, then rewire.

package com.bank.service;

public class ReverseLinkedListRecursive {
    public static ListNode reverseRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseRecursive(head.next);
        head.next.next = head;  // successor points back to current
        head.next = null;       // current no longer points forward
        return newHead;
    }
}

The key line head.next.next = head means: after the rest is reversed, the node that was originally after me must now point back to me.

What is the step-by-step trace?

For list 1 -> 2 -> 3:

Iterative:
- curr=1, prev=null. next=2. Flip: 1->null. prev=1, curr=2.
- curr=2, prev=1. next=3. Flip: 2->1. prev=2, curr=3.
- curr=3, prev=2. next=null. Flip: 3->2. prev=3, curr=null.
- Return prev=3. List: 3 -> 2 -> 1.

Recursive:
- reverse(1): calls reverse(2)
- reverse(2): calls reverse(3)
- reverse(3): base case, return 3. newHead=3.
- Back in reverse(2): 2.next.next = 2 means 3->2. 2.next=null. Return 3.
- Back in reverse(1): 1.next.next = 1 means 2->1. 1.next=null. Return 3.

How do the two approaches compare?

| Aspect | Iterative | Recursive |
|---|---|---|
| Time | O(n) | O(n) |
| Space | O(1) | O(n) stack frames |
| Stack overflow risk | None | Yes, on long lists |
| Readability | Clear loop | Elegant but tricky |
| Production preference | Yes | No (stack risk) |

What are common mistakes?

In the iterative version, advancing curr before saving next.

In the recursive version, forgetting head.next = null, which leaves the old first node pointing to the old second node, creating a cycle.

// Wrong recursive: creates a cycle
head.next.next = head;
// head.next still points to the old successor
// Now there is a cycle: head <-> head.next

// Correct: break the forward link
head.next.next = head;
head.next = null;

What are the edge cases?

- **Empty list (null)**: return null.
- **Single node**: return that node unchanged.
- **Two nodes**: `1 -> 2` becomes `2 -> 1`.

What should a senior engineer know?

The iterative reversal is a building block used inside many other algorithms:

• Palindrome check: reverse the second half and compare.
• Reverse in groups of k: reverse each k-node segment.
• Add two numbers: if stored in forward order, reverse first.

In production, always prefer the iterative version. The recursive version is for understanding the concept and for very short lists.

What are common interview follow-up questions?

• Reverse only a portion of the list (positions m to n). (Walk to position m, reverse n-m nodes, reconnect.)
• Reverse in groups of k. (Reverse each group iteratively, link groups together.)
• Can you reverse a doubly linked list? (Swap prev and next pointers for each node.)