Rotate a LinkedList
Mahabharata — The Chakravyuha Rotation — The Column Wraps Around
चक्रव्यूहस्य भ्रमणेन पंक्तिः परिवर्तते। पुच्छः शीर्षे आयाति — नूतनः आरम्भः॥
*Through the rotation of the Chakravyuha, the column transforms. The tail comes to the head — a new beginning emerges.*
The Story
Given a linked list, rotate it to the right by k places.
`1→2→3→4→5`, k=2 → `4→5→1→2→3`
Arjuna's chakravyuha formation needed to rotate k positions to the right — the last k warriors moved to the front.
**The elegant insight:** Rotating right by k = making the (n-k)th node the new tail and the (n-k+1)th node the new head.
**Algorithm:** 1. Find the length n and connect tail to head (make it circular) 2. Compute effective rotation: `k = k % n` (rotating n times = no rotation) 3. Find the new tail: it's at position `n - k - 1` from head (0-indexed), i.e., traverse `n - k - 1` steps 4. New head = new_tail.next 5. Break the cycle: new_tail.next = null
Trace: `1→2→3→4→5`, k=2, n=5 - k = 2%5 = 2 - New tail at step n-k-1 = 2 from head: 1→2→3 (node 3 is new tail) - New head = 3.next = 4 - Connect old tail 5 to head 1 (circular), then break at 3.next=null
Result: `4→5→1→2→3` ✓
Alternatively: after making circular, walk to position `n - k` and break there.
"The Chakravyuha doesn't truly destroy the formation," Arjuna noted. "It just reconnects the tail to the head and breaks at a new position."
The Step-by-Step Rotator
Perform k single rotations: each time, detach the tail and prepend it to the head. O(n*k) time.
public ListNode rotateRightBruteForce(ListNode head, int k) {
if (head == null) return null;
for (int i = 0; i < k; i++) {
ListNode prev = null, curr = head;
while (curr.next != null) { prev = curr; curr = curr.next; }
prev.next = null;
curr.next = head;
head = curr;
}
return head;
}Arjuna's Circular-Then-Break Wisdom
public ListNode rotateRight(ListNode head, int k) {
if (head == null) return null;
// Find length and tail
int len = 1;
ListNode tail = head;
while (tail.next != null) { tail = tail.next; len++; }
// Make circular
tail.next = head;
// Find new tail: (len - k%len - 1) steps from head
k = k % len;
int stepsToNewTail = len - k - 1;
ListNode newTail = head;
for (int i = 0; i < stepsToNewTail; i++) newTail = newTail.next;
// New head and break
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}Step-by-Step Walkthrough
1→2, k=3, n=2 k=3%2=1. steps=2-1-1=0. newTail=head=1. newHead=1.next=2. 1.next=null. Return 2→1 ✅ (one right rotation of [1,2] gives [2,1])
Deep Insight
**k=0 or k%n=0:** steps to new tail = n-1 → new tail = old tail → break there → list unchanged. Correct.
**Why k%n?** Rotating n times returns to original. k=7 on a 5-node list is same as k=2. The modulo handles this.
**Why `steps = len - k - 1` not `len - k`?** We want the NEW TAIL, which is 1 node before the new head. New head is at position n-k (1-indexed) from the start. New tail is at position n-k-1 (0-indexed from 0 = n-k steps-1).
Alternative: walk `len - k` steps from circular head to new head directly.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n×k) | O(1) | k single-step rotations |
| Optimal | O(n) | O(1) | One pass for length + one walk to cut point |
Pattern Recognition
✅ Rotate right by k ✅ Make circular → find cut point → break ✅ Effective k = k % len ✅ New tail at position len-k-1, new head = new_tail.next **LeetCode Trigger Phrases:** → "rotate list" by k positions → "right rotation" of linked list → k % len to handle large k
Bhagavad Gita (Dhyana Shloka)
नित्यं विभुमनापेक्षं परिपूर्णमजं विभुम्। अव्यक्तमव्ययं शान्तं प्रणमामि परात्परम्॥
I bow to the Supreme beyond the Supreme — eternal, all-pervading, independent, perfect, unborn, imperishable, peaceful, and unmanifest.
Connection: The chakravyuha — the circular formation — embodies the eternal cycle. In rotation, the tail becomes head, the end becomes beginning. The algorithm makes this cosmic truth explicit: first it closes the circle (tail.next=head), then chooses a new starting point. Like the eternal cycle where endings birth new beginnings, the rotation finds the new head not by searching but by measuring the precise point where the cosmic circle must be opened.