Reverse every K-element Sub-list
Mahabharata — Drona's K-Platoon Reversal — Flip Every Regiment of K Warriors
क-संख्यकानां योधानां प्रत्येकं दलं विपरीतयेत्। यदि क पूर्णं न हो — तत् यथावत् तिष्ठेत्॥
*Every group of k warriors — reverse it. If a group is incomplete — leave it as is.*
The Story
Given a linked list and a number k, reverse every k consecutive nodes. If remaining nodes are fewer than k, leave them as-is.
For `1→2→3→4→5`, k=2: `2→1→4→3→5` For `1→2→3→4→5`, k=3: `3→2→1→4→5`
Drona divided his army into platoons of exactly k warriors. Each complete platoon reversed its formation. Any incomplete final platoon stayed in original order.
**Algorithm — iterative with group counting:** 1. Count k nodes from current position. If fewer than k remain, stop. 2. Reverse those k nodes (using lr-1's technique: prev/curr/next) 3. Connect the reversed group: - The node before the group (`prev`) should now point to the new head of the reversed group - The old head (now tail) should point to the start of the next group 4. Advance: `prev` = old head (tail of reversed group), `curr` = next unconsumed node
**Recursive approach (cleaner):** ``` Count k nodes. If < k: return head as-is. Reverse first k nodes (lr-1 style). newHead.next = reverseKGroup(next_group_start, k) return old_tail (which is the new head of this reversed group) ```
Trace `1→2→3→4→5`, k=3: - Count 3: enough. Reverse [1,2,3] → 3→2→1. Connect: 1.next = reverseKGroup(4,3) - Count 2 from 4: only 2 < 3. Return 4 (unchanged) - 1.next = 4. Result: 3→2→1→4→5 ✓
The recursive solution is elegant and O(n/k) stack space — one frame per group.
The List-to-Array Approach
Collect all values in array. Reverse each k-chunk in-place. Rebuild list. O(n) time, O(n) space.
public ListNode reverseKGroupBruteForce(ListNode head, int k) {
List<Integer> vals = new ArrayList<>();
for (ListNode c = head; c != null; c = c.next) vals.add(c.val);
for (int i = 0; i + k <= vals.size(); i += k) {
int l = i, r = i + k - 1;
while (l < r) { Collections.swap(vals, l++, r--); }
}
ListNode curr = head;
for (int v : vals) { curr.val = v; curr = curr.next; }
return head;
}Drona's Recursive Group Wisdom
public ListNode reverseKGroup(ListNode head, int k) {
// Count k nodes
ListNode curr = head;
int count = 0;
while (curr != null && count < k) { curr = curr.next; count++; }
if (count < k) return head; // Not enough nodes — leave unchanged
// Reverse k nodes starting from head
ListNode prev = null, node = head;
for (int i = 0; i < k; i++) {
ListNode next = node.next;
node.next = prev;
prev = node;
node = next;
}
// head is now the tail of the reversed group
// node is the start of the next group
head.next = reverseKGroup(node, k);
return prev; // prev is the new head of this reversed group
}Step-by-Step Walkthrough
1→2→3→4, k=4 Count 4: enough. Reverse [1,2,3,4]→4→3→2→1. 1.next=reverseKGroup(null,4)=null. Return 4→3→2→1 ✅ 1→2→3, k=4 Count: only 3<4. Return 1→2→3 unchanged ✅
Deep Insight
**Iterative alternative:** Use a dummy node. For each group: find kth node, reverse the group, reconnect dummy/prev to new group head, advance.
**Stack space:** Recursive uses O(n/k) stack frames (one per group). For k=1, O(n); for k=n, O(1).
**lr-3 is lr-4 with k=2.** The k-group problem subsumes pair swapping.
**The crucial connection:** After reversing, `head` (original first) becomes the tail. We connect it to the result of the recursive call on the next group. This is why we keep a reference to `head` before the reversal loop.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Array storage for all values |
| Optimal | O(n) | O(n/k) | Recursive stack — one frame per group. Iterative gives O(1) |
Pattern Recognition
✅ Reverse every k nodes ✅ Check k available before reversing ✅ Tail of reversed group connects to next reversal ✅ Recursive: elegant; Iterative: O(1) space **LeetCode Trigger Phrases:** → "reverse nodes in k-group" → "reverse every k elements" → Leave last group unchanged if incomplete
Bhagavad Gita 3.15
कर्म ब्रह्मोद्भवं विद्धि ब्रह्माक्षरसमुद्भवम्। तस्मात्सर्वगतं ब्रह्म नित्यं यज्ञे प्रतिष्ठितम्॥
Know that action (karma) arises from Brahman, and Brahman from the Imperishable. Therefore, the all-pervading Brahman is always present in the sacrifice.
Connection: Each group of k is a complete unit of action — a yagya (sacrifice) unto itself. Only complete groups are reversed; incomplete groups (fewer than k warriors) are left in their natural order, just as an incomplete ritual cannot be performed. The algorithm respects this completeness: it counts first before committing to action, proceeding only when the full complement is present.