Reverse Nodes in Even Length Groups
Mahabharata — The Vyuha of Even Platoons — Only Even-Numbered Formations Reverse
सम-दलं विपरीतयेत्, विषम-दलं यथावत्। एवं व्यूहः विचित्रः — युगलस्य नियमेन॥
*Reverse the even-numbered groups, leave the odd ones as is. Thus the formation is transformed — by the law of pairs.*
The Story
The linked list is split into groups of sizes 1, 2, 3, 4, ... (group i has i nodes, unless the last group is shorter). Reverse the nodes in each group that has an EVEN length. Leave odd-length groups unchanged.
For `5→2→6→3→9→1→7→3→8→4` (10 nodes): - Group 1 (size 1): [5] — odd length → leave: [5] - Group 2 (size 2): [2,6] — even → reverse: [6,2] - Group 3 (size 3): [3,9,1] — odd → leave: [3,9,1] - Group 4 (size 4): [7,3,8,4] — even → reverse: [4,8,3,7]
Result: `5→6→2→3→9→1→4→8→3→7`
**Algorithm:** Keep a `prev` pointer (starts at dummy). For group number g=1,2,3,...: 1. Walk up to g nodes from prev, tracking actual length (may be less if list ends) 2. If actual length is even: reverse the group (like lr-2's sub-list reversal) 3. If odd: just advance prev to end of group 4. g++, continue
The sub-list reversal uses lr-2's head-insertion technique: repeatedly take next node and insert at front of group.
This is the most complex LinkedList Reversal problem — combining group traversal with conditional sub-list reversal.
The Array Rebuilder
Collect all values. Split into groups. Reverse even-length groups in the array. Rebuild list. O(n) time, O(n) space.
public ListNode reverseEvenLengthGroupsBruteForce(ListNode head) {
List<Integer> vals = new ArrayList<>();
for (ListNode c = head; c != null; c = c.next) vals.add(c.val);
int i = 0, g = 1;
while (i < vals.size()) {
int end = Math.min(i + g, vals.size());
int len = end - i;
if (len % 2 == 0) {
int l = i, r = end - 1;
while (l < r) { Collections.swap(vals, l++, r--); }
}
i += len; g++;
}
ListNode curr = head;
for (int v : vals) { curr.val = v; curr = curr.next; }
return head;
}The Group-Reverse Wisdom
public ListNode reverseEvenLengthGroups(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
int g = 1;
while (prev.next != null) {
// Find actual length of group g
int len = 0;
ListNode curr = prev;
while (len < g && curr.next != null) { curr = curr.next; len++; }
// If even length: reverse using head-insertion
if (len % 2 == 0) {
ListNode tail = prev.next; // will become tail after reversal
for (int i = 0; i < len - 1; i++) {
ListNode next = tail.next;
tail.next = next.next;
next.next = prev.next;
prev.next = next;
}
prev = tail; // tail is now the end of the reversed group
} else {
prev = curr; // advance prev to end of odd group
}
g++;
}
return dummy.next;
}Step-by-Step Walkthrough
1→2→3→4 (4 nodes) G1(1): [1] odd. prev=1 G2(2): [2,3] even. Reverse: 3→2. prev=2 G3 target=3, but only [4] remains. len=1 odd. prev=4. Result: 1→3→2→4 ✅
Deep Insight
**Why head-insertion for sub-list reversal?** Same as lr-2: repeatedly pull the next node after tail and place it right after prev. After len-1 pulls, the group is fully reversed. `tail` (original first of group) ends up as the last — we keep it as `prev` for the next group.
**The last group's actual length may differ from g:** A list of 10 nodes with groups 1,2,3,4 — the 4th group has exactly 4 nodes (even). But a list of 9 nodes — the 4th group would only have 3 nodes (odd). The `len` variable captures this correctly.
**Why the most complex lr problem?** It requires both group management (variable-size traversal) and conditional in-place reversal — combining lr-2 and lr-4 concepts.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Array for all values |
| Optimal | O(n) | O(1) | In-place group-by-group reversal |
Pattern Recognition
✅ Groups of size 1,2,3,...; reverse even-length groups ✅ Track actual group length (may be less than g at end) ✅ Head-insertion for even groups, skip for odd ✅ prev tracks tail of last processed group **LeetCode Trigger Phrases:** → "reverse nodes in even length groups" → Variable-size groups with conditional reversal → Most complex LinkedList Reversal variant
Bhagavad Gita 2.59
विषया विनिवर्तन्ते निराहारस्य देहिनः। रसवर्जं रसोऽप्यस्य परं दृष्ट्वा निवर्तते॥
The objects of sense turn away from the embodied soul who ceases to feed them; but the taste for them remains. This too ceases when he sees the Supreme.
Connection: The algorithm discriminates between even and odd groups — acting on some, leaving others untouched. Like the sage who, after seeing the Supreme, no longer responds to objects of sense while still perceiving them, the algorithm traverses all groups with full awareness but reverses only those that meet the even-length condition. Discernment (viveka) — knowing when to act and when to pass — is the essence of both the algorithm and the Gita's teaching.