Reverse a Sub-list
Mahabharata — The Tactical Reversal — Flipping Only the Central Regiment
सम्पूर्णं नहि — केवलं मध्यभागम् विपरीतं कुरु। पूर्वं च परं च यथावत् — मध्यं परावर्तय॥
*Not the whole — only the middle section reversed. The beginning and end unchanged — reverse only the middle.*
The Story
Given the head of a singly linked list and two positions `left` and `right`, reverse the nodes from position `left` to `right` (1-indexed). Return the modified list.
For `head = 1→2→3→4→5`, left=2, right=4: Result: `1→4→3→2→5`
Krishna's tactical maneuver: only the regiment from position 2 to 4 reverses, while 1 and 5 remain.
**Four-pointer technique:** 1. `dummy` node before head (handles edge case where left=1) 2. Walk to node at position `left-1`: this is `prev` (the node just before the reversal zone) 3. `curr` = prev.next (first node to reverse) 4. Reverse `right - left` times using "head insertion" technique: - Save curr.next as `next` - `curr.next = next.next` (curr stays, skip next) - `next.next = prev.next` (next points to current front of sublist) - `prev.next = next` (prev now points to next — new front)
Trace: `1→2→3→4→5`, left=2, right=4 dummy→1→2→3→4→5. prev=1, curr=2.
Iteration 1 (i=1): next=3. curr.next=4 (2→4). next.next=2 (3→2). prev.next=3 (1→3). List: 1→3→2→4→5. Iteration 2 (i=2): next=4. curr.next=5 (2→5). next.next=3 (4→3). prev.next=4 (1→4). List: 1→4→3→2→5.
Result: `1→4→3→2→5` ✓
This "head insertion" approach is elegant — instead of tracking multiple pointers for a sublist reversal, we repeatedly insert the next node at the front of the growing reversed section.
The Collector's Approach
Collect node values, reverse the subarray slice, rebuild. O(n) time, O(n) space.
public ListNode reverseBetweenBruteForce(ListNode head, int left, int right) {
List<Integer> vals = new ArrayList<>();
ListNode curr = head;
while (curr != null) { vals.add(curr.val); curr = curr.next; }
int l = left - 1, r = right - 1;
while (l < r) { Collections.swap(vals, l++, r--); }
curr = head;
for (int v : vals) { curr.val = v; curr = curr.next; }
return head;
}Krishna's Head-Insertion Wisdom
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
// Move prev to node just before position 'left'
for (int i = 1; i < left; i++) prev = prev.next;
ListNode curr = prev.next;
// Reverse by head-insertion
for (int i = 0; i < right - left; i++) {
ListNode next = curr.next;
curr.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next;
}Step-by-Step Walkthrough
1→2→3→4→5, left=1, right=3 dummy→1→2→3→4→5. prev=dummy, curr=1. Iter 1: next=2. 1→3. 2→1. dummy→2. List: dummy→2→1→3→4→5. Iter 2: next=3. 1→4. 3→2. dummy→3. List: dummy→3→2→1→4→5. Return 3→2→1→4→5 ✅
Deep Insight
**Head-insertion technique explained:** At each step, we take the node immediately after `curr` and insert it at the front of the reversed sublist (right after `prev`).
After each insertion: - `curr` stays as the tail of the growing reversed section - The new front of the reversed section is `prev.next`
**Why dummy node?** If `left=1`, there's no node before the reversal start. The dummy node provides a consistent `prev` without special-casing.
**Loop count:** We do `right - left` insertions (not `right - left + 1`) because `curr` is already in its initial position from before the loop.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Array for all values |
| Optimal | O(n) | O(1) | One pass to find prev, one loop for reversal |
Pattern Recognition
✅ Reverse sublist from position left to right ✅ Dummy node + advance to left-1 ✅ Head-insertion: take next, insert at front ✅ Loop (right-left) times **LeetCode Trigger Phrases:** → "reverse linked list II" → "reverse between positions left and right" → Sublist reversal in-place
Bhagavad Gita 18.46
यतः प्रवृत्तिर्भूतानां येन सर्वमिदं ततम्। स्वकर्मणा तमभ्यर्च्य सिद्धिं विन्दति मानवः॥
From Whom all beings arise and by Whom all this is pervaded — worshipping Him through one's own proper duty, a person finds perfection.
Connection: The sublist reversal touches only what it must — the section between left and right — while leaving the surrounding list undisturbed. Like dharmic action that operates within its proper domain without interference, the head-insertion technique transforms precisely the designated section. The dummy node that enables left=1 to work seamlessly echoes the unseen divine principle that supports all action without imposing itself.