Definition
- In-place reversal walks the list once, redirecting each node's
nextpointer to the previous node. - Three references:
previous(initially null),current(initially head), and a savednext. - At each node:
next = current.next,current.next = previous,previous = current,current = next. - When
currentbecomes null,previousis the new head. - No new nodes allocated, so space is O(1).
- This skeleton powers sublist reversal, k-group reversal, and rotation.
At the National Bank of India, transaction slips are stored as a singly linked chain in oldest-first insertion order. To display them newest-first for a customer statement, a clerk unclips each slip and re-clips it to the slip that came before, moving down the chain once. At the end, the last slip is the new front of the chain.
Understanding the Concepts
What is the Reverse LinkedList problem?
Given the head of a singly linked list, reverse it in place so that the last node becomes the new head and all links point backward. Return the new head. Do it in O(N) time and O(1) extra space. This is LeetCode 206.
For example, reversing 1 -> 2 -> 3 -> null gives 3 -> 2 -> 1 -> null.
How does the three-pointer algorithm work?
The algorithm maintains three pointers: previous (starts as null), current (starts at head), and a temporary next to save the forward link before overwriting it.
package com.bank.model;
public class TransactionNode {
public long amount;
public String description;
public TransactionNode next;
public TransactionNode(long amount, String description) {
this.amount = amount;
this.description = description;
}
}
package com.bank.service;
import com.bank.model.TransactionNode;
public class LinkedListReverseService {
/**
* Reverses a transaction chain in place for newest-first display.
* Used by the National Bank of India statement generation.
*/
public static TransactionNode reverse(TransactionNode head) {
TransactionNode previous = null;
TransactionNode current = head;
while (current != null) {
TransactionNode next = current.next; // Save forward link
current.next = previous; // Reverse the link
previous = current; // Advance previous
current = next; // Advance current
}
return previous; // New head
}
public static void main(String[] args) {
TransactionNode t1 = new TransactionNode(10000, "Deposit");
TransactionNode t2 = new TransactionNode(-5000, "Withdrawal");
TransactionNode t3 = new TransactionNode(20000, "Transfer");
t1.next = t2;
t2.next = t3;
System.out.println("Before: ");
printList(t1);
TransactionNode newHead = reverse(t1);
System.out.println("After reversal: ");
printList(newHead);
}
static void printList(TransactionNode head) {
TransactionNode curr = head;
while (curr != null) {
System.out.print("Rs." + curr.amount + " (" + curr.description + ")");
if (curr.next != null) System.out.print(" -> ");
curr = curr.next;
}
System.out.println();
}
}
javac -d out com/bank/model/TransactionNode.java com/bank/service/LinkedListReverseService.java
java -cp out com.bank.service.LinkedListReverseService
Before:
Rs.10000 (Deposit) -> Rs.-5000 (Withdrawal) -> Rs.20000 (Transfer)
After reversal:
Rs.20000 (Transfer) -> Rs.-5000 (Withdrawal) -> Rs.10000 (Deposit)
Why is saving next mandatory?
The instant you execute current.next = previous, you overwrite the only reference to the rest of the list. Without saving next first, the remaining nodes become unreachable and are effectively lost.
// WRONG: loses the rest of the list
current.next = previous; // forward link destroyed!
current = current.next; // this is now 'previous', not the next node!
// CORRECT: save first
TransactionNode next = current.next; // save forward link
current.next = previous; // now safe to overwrite
current = next; // move to saved next
How does the recursive alternative work?
Recursion reverses the list by first reaching the tail (base case: node is null or node.next is null), then rewiring links on the way back.
public static TransactionNode reverseRecursive(TransactionNode head) {
if (head == null || head.next == null) {
return head; // Base case: empty or single node
}
TransactionNode newHead = reverseRecursive(head.next);
head.next.next = head; // Reverse the link
head.next = null; // Remove forward link
return newHead;
}
The recursive version is elegant but uses O(N) stack space, making it unsuitable for very long lists in production.
How is this the foundation for reversal variants?
The three-pointer skeleton is the basis for all in-place reversal problems. The only differences are where you start, where you stop, and how you re-stitch the boundaries.
| Variant | Start | Stop | Extra work |
|---|---|---|---|
| Full reversal | Head | Null | None |
| Sublist reversal | Position m | Position n | Stitch before/after |
| K-group reversal | Each group start | After K nodes | Stitch groups |
| Rotate list | Varies | Varies | Find new head |
What are the edge cases?
Several edge cases require attention.
- Empty list (null): return null.
- Single node: already reversed, return the node.
- Two nodes: one swap operation.
- Cycle detection: if the list has a cycle, the algorithm loops forever. Assume no cycles.
package com.bank.core;
public class ReverseEdgeCases {
public static void main(String[] args) {
// Null list
System.out.println(reverse(null)); // null
// Single node
TransactionNode single = new TransactionNode(5000, "Solo");
TransactionNode result = reverse(single);
System.out.println(result.amount); // 5000
}
static TransactionNode reverse(TransactionNode head) {
TransactionNode prev = null, curr = head;
while (curr != null) {
TransactionNode next = curr.next;
curr.next = prev; prev = curr; curr = next;
}
return prev;
}
}
null
5000
What is the time and space complexity?
Time is O(N): one pass through the list. Space is O(1): three pointer variables, no new nodes. The iterative version is preferred over recursion for production because it avoids O(N) stack depth on long lists.
What should a senior engineer know?
A senior engineer should understand these deeper aspects.
- Iterative vs recursive trade-off: iterative is O(1) space; recursive is O(N) stack. For production lists that could be millions of nodes, iterative is the only safe choice.
- Sentinel nodes: some implementations use a dummy head node to simplify boundary handling, but in-place reversal typically does not need one.
- Immutable lists: in functional programming, lists are reversed by building a new list. In-place reversal is a mutable-data-structure operation.
- Thread safety: in-place reversal mutates the structure, so it is not safe to call concurrently. For concurrent access, copy-on-write or immutable reversal is needed.
What are common interview follow-up questions?
Interviewers often extend this problem.
- Reverse a sublist: reverse nodes between positions m and n.
- Reverse in k-groups: reverse every k consecutive nodes.
- Palindrome linked list: reverse the second half and compare with the first half.
- Rotate a list by k positions: find the new head after rotation.
Visual Overview
Original: 10000 -> -5000 -> 20000 -> null
Step 1: prev=null curr=10000 next=-5000
10000.next = null (was -5000)
prev=10000 curr=-5000
Step 2: prev=10000 curr=-5000 next=20000
-5000.next = 10000 (was 20000)
prev=-5000 curr=20000
Step 3: prev=-5000 curr=20000 next=null
20000.next = -5000 (was null)
prev=20000 curr=null -> STOP
Result: 20000 -> -5000 -> 10000 -> null
prev is the new head
Pointer state at each step:
┌────────┬──────────┬──────────┬──────────┐
│ Step │ previous │ current │ next │
├────────┼──────────┼──────────┼──────────┤
│ Init │ null │ 10000 │ - │
│ 1 │ 10000 │ -5000 │ -5000 │
│ 2 │ -5000 │ 20000 │ 20000 │
│ 3 │ 20000 │ null │ null │
└────────┴──────────┴──────────┴──────────┘
Key Takeaway
Reversing a singly linked list in place is the foundation of the entire in-place reversal pattern. It rests on three pointers: previous (trailing behind), current (being processed), and a saved next (preserving the forward link before it is overwritten). At each node, you save next, reverse the link by pointing current back to previous, then slide both pointers forward. When current falls off the end, previous is the new head.
The saved next pointer is not optional. The instant you reassign current.next to previous, you destroy the only forward reference to the rest of the list. Without saving it first, the remaining nodes are lost. This runs in O(N) time and O(1) space, and the iterative version is preferred over recursion for production because recursion would consume O(N) stack space on long lists.
At the National Bank of India, Rajesh used this to render transaction statements newest-first. Transaction slips were stored as a singly linked chain in oldest-first insertion order, and the chains could be very long. The three-pointer in-place reversal flipped each chain in a single pass with no extra allocation, which was critical for memory-constrained batch processing.
The senior-level insight is that this same three-pointer skeleton, with different start and stop conditions, powers sublist reversal, k-group reversal, and rotation. Mastering the base case means all the variants follow naturally.
Remember one sentence: save next, reverse the link, advance both pointers, and previous ends as the new head.
---