Reverse a LinkedList
Mahabharata — Arjuna's Retreat — Reversing the Column of Warriors
यत्र श्रेणी प्रतिलोमा करणीया। प्रत्येकः पूर्वं दर्शयेत् — तत् विपरीतं व्यूहम्॥
*Where the column must be reversed — let each warrior face the one behind. That forms the inverted formation.*
The Story
The simplest and most fundamental linked list operation: reverse a singly linked list in-place.
1 → 2 → 3 → 4 → 5 → null becomes 5 → 4 → 3 → 2 → 1 → null
Bhima led the column. Each warrior was told: "When I say reverse, turn around and face the warrior who was behind you."
The iterative algorithm uses three pointers: - `prev` (previous warrior, starts as null) - `curr` (current warrior, starts at head) - `next` (saves the next pointer before we reverse it)
Each step: 1. Save curr.next in `next` (remember who's behind) 2. curr.next = prev (point backward) 3. prev = curr (advance prev) 4. curr = next (advance curr)
Trace: head = 1→2→3→4→5
- prev=null, curr=1: next=2. 1.next=null. prev=1. curr=2. - prev=1, curr=2: next=3. 2.next=1. prev=2. curr=3. - prev=2, curr=3: next=4. 3.next=2. prev=3. curr=4. - prev=3, curr=4: next=5. 4.next=3. prev=4. curr=5. - prev=4, curr=5: next=null. 5.next=4. prev=5. curr=null. - curr=null → stop. New head = prev = 5.
Result: 5→4→3→2→1→null ✓
This is the cornerstone of the LinkedList Reversal pattern. Every subsequent problem (lr-2 through lr-6) builds on this simple operation.
The Collector's Instinct
Collect all node values in a stack. Rebuild the list by popping. O(n) time, O(n) space.
public ListNode reverseListBruteForce(ListNode head) {
Deque<Integer> stack = new ArrayDeque<>();
ListNode curr = head;
while (curr != null) { stack.push(curr.val); curr = curr.next; }
ListNode dummy = new ListNode(0), node = dummy;
while (!stack.isEmpty()) {
node.next = new ListNode(stack.pop());
node = node.next;
}
return dummy.next;
}Bhima's In-Place Reversal Wisdom
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // Save next before overwriting
curr.next = prev; // Reverse the link
prev = curr; // Advance prev
curr = next; // Advance curr
}
return prev; // prev is the new head
}Step-by-Step Walkthrough
head: 1→null (single node) prev=null, curr=1: next=null. 1.next=null. prev=1. curr=null. Return prev=1: 1→null ✅
Deep Insight
**Recursive alternative:** ```java public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } ``` Elegant but O(n) space on the call stack.
**The iterative approach is preferred:** O(1) space.
**Foundation for all list reversal problems:** Every lr-2 through lr-6 problem uses this core operation on a sublist, full list, or with additional logic. Master this simple traversal and the rest follow naturally.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Stack stores all values |
| Optimal | O(n) | O(1) | Three pointers, single pass |
Pattern Recognition
✅ Reverse entire linked list in-place ✅ Three pointers: prev=null, curr=head, next=temp ✅ Single pass: save-next → reverse → advance ✅ Return prev (new head) **LeetCode Trigger Phrases:** → "reverse linked list" → "reverse all nodes" → Foundation for all reversal sub-problems
Bhagavad Gita 11.35
नमस्कृत्वा पुनरेवाह कृष्णं संहृष्टमानसः। सगद्गदं भीतभीतः प्रणम्य च पुनः पुनः॥
Having bowed down again with joy, Krishna spoke to him again, trembling and overwhelmed, bowing repeatedly.
Connection: The reversal is an act of complete turning — each node looks back to face what was behind it. Like Arjuna facing Krishna after the great vision, turning completely to see the source, the linked list reversal makes each node point to its predecessor. The new head (prev at the end) is the one who was last, now elevated to lead — just as the last becomes first when perspective is truly reversed.