94. Rotate List
🔗 LeetCode Problem: 61. Rotate List
📊 Difficulty: Medium
🏷️ Topics: Linked List, Two Pointers
Problem Statement
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Visual:
Original: 1 → 2 → 3 → 4 → 5 → null
Rotate 1: 5 → 1 → 2 → 3 → 4 → null
Rotate 2: 4 → 5 → 1 → 2 → 3 → null ✓
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Visual:
k = 4, but length = 3
k % 3 = 1 (only need 1 rotation)
Original: 0 → 1 → 2 → null
Rotate 1: 2 → 0 → 1 → null ✓
Constraints:
- The number of nodes in the list is in the range [0, 500].
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10^9
🌟 ELI5: The Simple Idea!
Think of a circular track:
Original: [1, 2, 3, 4, 5]
Rotate right by 2 means:
- Take last 2 elements
- Move them to front
Visual:
[1, 2, 3] [4, 5]
↑_____↑
Move these to front
[4, 5] [1, 2, 3] ✓
Key Insight: Make it circular, then break at the right spot!
Step 1: Connect tail to head (make circular)
1 → 2 → 3 → 4 → 5 → 1 → 2 → 3 → ...
↑___________________|
Step 2: Find new tail (length - k positions from start)
For k=2, length=5:
New tail at position: 5 - 2 = 3
1 → 2 → 3 → 4 → 5 → 1
↑
new tail
Step 3: Break after new tail
New head = new_tail.next = 4
new_tail.next = null
4 → 5 → 1 → 2 → 3 → null ✓
🎨 Visual Understanding
The Rotation Process
Example: [1,2,3,4,5], k = 2
═══════════════════════════════════════════════════════════════
Original List
═══════════════════════════════════════════════════════════════
1 → 2 → 3 → 4 → 5 → null
Length = 5
═══════════════════════════════════════════════════════════════
Step 1: Make Circular
═══════════════════════════════════════════════════════════════
Connect tail to head:
┌─────────────────────────┐
↓ │
1 → 2 → 3 → 4 → 5 ────────────┘
Now: 1 → 2 → 3 → 4 → 5 → 1 → 2 → 3 → ...
(circular, infinite)
═══════════════════════════════════════════════════════════════
Step 2: Find New Tail Position
═══════════════════════════════════════════════════════════════
k = 2 (rotate by 2)
length = 5
Effective rotations: k % length = 2 % 5 = 2
New tail position: length - k = 5 - 2 = 3
(Count from start: position 3 is node 3)
┌─────────────────────────┐
↓ │
1 → 2 → 3 → 4 → 5 ────────────┘
↑
new tail
═══════════════════════════════════════════════════════════════
Step 3: Break at New Tail
═══════════════════════════════════════════════════════════════
New head = new_tail.next = 4
Break: new_tail.next = null
4 → 5 → 1 → 2 → 3 → null ✓
This is our answer!
Example with k > length
Example: [1,2,3], k = 4
Length = 3
k = 4
Rotations needed: 4 % 3 = 1
(Rotating 3 times gives same list, only need 1 more)
Original: 1 → 2 → 3
Rotate 1: 3 → 1 → 2 ✓
Using formula:
New tail position: 3 - 1 = 2
1 → 2 → 3 (circular)
↑
new tail at position 2
New head = 3
Break after 2
3 → 1 → 2 → null ✓
🎯 Approach 1: Make Circular + Break ⭐
The Optimal Solution
Algorithm:
1. Find length and tail (traverse entire list)
2. Connect tail to head (make circular)
3. Calculate effective rotations: k = k % length
4. Find new tail: move (length - k) steps from head
5. Break circle: new_head = new_tail.next, new_tail.next = null
Implementation
/**
* Make circular, then break at correct position
* Time: O(n), Space: O(1)
*/
public ListNode rotateRight(ListNode head, int k) {
// Edge cases
if (head == null || head.next == null || k == 0) {
return head;
}
// Step 1: Find length and tail
ListNode tail = head;
int length = 1;
while (tail.next != null) {
tail = tail.next;
length++;
}
// Step 2: Make circular
tail.next = head;
// Step 3: Optimize k (handle k > length)
k = k % length;
// If k is 0, no rotation needed
if (k == 0) {
tail.next = null; // Break circle
return head;
}
// Step 4: Find new tail (length - k steps from start)
int stepsToNewTail = length - k;
ListNode newTail = head;
for (int i = 1; i < stepsToNewTail; i++) {
newTail = newTail.next;
}
// Step 5: Break circle
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
⏰ Time: O(n) - Two passes: find length, find new tail
💾 Space: O(1) - Only pointers
🔍 Super Detailed Dry Run
Example: head = [1,2,3,4,5], k = 2
Goal: Rotate right by 2 → [4,5,1,2,3]
Initial:
head → 1 → 2 → 3 → 4 → 5 → null
═══════════════════════════════════════════════════════════════
STEP 1: Find Length and Tail
═══════════════════════════════════════════════════════════════
tail = head (node 1)
length = 1
Traverse:
Iteration 1: tail = 2, length = 2
Iteration 2: tail = 3, length = 3
Iteration 3: tail = 4, length = 4
Iteration 4: tail = 5, length = 5
Iteration 5: tail.next = null, exit
Result:
length = 5
tail = node 5
State:
1 → 2 → 3 → 4 → 5 → null
↑
tail
═══════════════════════════════════════════════════════════════
STEP 2: Make Circular
═══════════════════════════════════════════════════════════════
tail.next = head
node 5's next = node 1
State (circular):
┌─────────────────────────┐
↓ │
1 → 2 → 3 → 4 → 5 ────────────┘
List is now circular (infinite)
═══════════════════════════════════════════════════════════════
STEP 3: Optimize k
═══════════════════════════════════════════════════════════════
k = k % length
k = 2 % 5 = 2
k != 0, continue with rotation
═══════════════════════════════════════════════════════════════
STEP 4: Find New Tail
═══════════════════════════════════════════════════════════════
Steps to new tail: length - k = 5 - 2 = 3
Start at head, move 3-1 = 2 steps
newTail = head (node 1)
Move step 1: newTail = 2
Move step 2: newTail = 3
Result:
newTail = node 3
┌─────────────────────────┐
↓ │
1 → 2 → 3 → 4 → 5 ────────────┘
↑
newTail
═══════════════════════════════════════════════════════════════
STEP 5: Break Circle
═══════════════════════════════════════════════════════════════
newHead = newTail.next = node 4
newTail.next = null
Before break:
┌─────────────────────────┐
↓ │
1 → 2 → 3 → 4 → 5 ────────────┘
↑ ↑
newTail newHead
After break:
4 → 5 → 1 → 2 → 3 → null
↑
newHead
═══════════════════════════════════════════════════════════════
Return Result
═══════════════════════════════════════════════════════════════
Return: newHead (node 4)
Final list: 4 → 5 → 1 → 2 → 3 → null ✓
Result: [4, 5, 1, 2, 3]
Example 2: head = [0,1,2], k = 4
Length = 3
k = 4 % 3 = 1
Steps to new tail: 3 - 1 = 2
Original: 0 → 1 → 2 → null
Make circular:
┌─────────────┐
↓ │
0 → 1 → 2 ────────┘
Move 1 step from head:
newTail = 1 (move 2-1 = 1 step)
But we start at head (0), move 1 step:
newTail = 1
Wait, let me recalculate:
stepsToNewTail = 3 - 1 = 2
Start at head (0)
Move (2-1) = 1 time
newTail = 1
Actually in the loop: for (i = 1; i < 2; i++)
Runs once: newTail = newTail.next = 1
Hmm, let me trace more carefully:
stepsToNewTail = 2
newTail starts at head (position 1)
for (i = 1; i < 2; i++) // i goes 1
newTail = newTail.next (position 2)
So newTail at position 2 (node 1)
┌─────────────┐
↓ │
0 → 1 → 2 ────────┘
↑
newTail
newHead = newTail.next = 2
newTail.next = null
Result: 2 → 0 → 1 → null ✓
🎯 Key Insights
Insight 1: Why k % length?
Example: [1,2,3], k = 100
Rotating 3 times brings back to original
So rotating 100 times = rotating 100 % 3 = 1 time
100 rotations = 33 full cycles + 1 rotation
Only the remainder matters!
k % length gives minimum rotations needed
Insight 2: Why length - k?
Rotate RIGHT by k = Move last k elements to front
Example: [1,2,3,4,5], k = 2
Last 2: [4,5]
Move to front: [4,5,1,2,3]
New head is at position: length - k + 1
New tail is at position: length - k
For length=5, k=2:
New tail at: 5 - 2 = 3 (node 3)
New head at: position 4 (node 4)
Circular approach:
Walk (length - k) steps to find new tail
New head = new_tail.next
Insight 3: Why make circular?
Without circular:
Need to:
1. Find new tail (position length - k)
2. Save new head (new_tail.next)
3. Break: new_tail.next = null
4. Find old tail
5. Connect: old_tail.next = old head
Complex!
With circular:
1. Make circular (one operation)
2. Find new tail
3. Break circle
Simpler and cleaner!
🎯 Approach 2: Two Pointers (Without Circular)
Alternative Without Making Circular
/**
* Two pointers approach without circular
* Time: O(n), Space: O(1)
*/
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// Find length
int length = 0;
ListNode curr = head;
while (curr != null) {
length++;
curr = curr.next;
}
// Optimize k
k = k % length;
if (k == 0) return head;
// Find new tail: at position (length - k)
ListNode newTail = head;
for (int i = 1; i < length - k; i++) {
newTail = newTail.next;
}
// Find old tail
ListNode oldTail = newTail;
while (oldTail.next != null) {
oldTail = oldTail.next;
}
// Reconnect
ListNode newHead = newTail.next;
newTail.next = null;
oldTail.next = head;
return newHead;
}
Why circular is better: One traversal to tail, then circular. This needs two traversals.
⚠️ Common Mistakes
Mistake 1: Not handling k > length
// ❌ WRONG - Infinite loops or wrong answer
// k = 100, length = 3
// Tries to rotate 100 times!
// ✓ CORRECT - Optimize first
k = k % length;
Mistake 2: Off-by-one in new tail position
// ❌ WRONG
for (int i = 0; i < length - k; i++) {
newTail = newTail.next;
}
// Moves one too many times!
// ✓ CORRECT - Start i at 1
for (int i = 1; i < length - k; i++) {
newTail = newTail.next;
}
Mistake 3: Forgetting to break circle when k = 0
// ❌ WRONG - Returns circular list!
k = k % length;
if (k == 0) {
return head; // But tail.next = head!
}
// ✓ CORRECT - Break before return
if (k == 0) {
tail.next = null;
return head;
}
Mistake 4: Not finding tail correctly
// ❌ WRONG - Off by one
while (tail != null) { // tail becomes null!
tail = tail.next;
}
// ✓ CORRECT
while (tail.next != null) {
tail = tail.next;
}
// Now tail points to last node
Mistake 5: Wrong calculation for new tail position
// ❌ WRONG - Confusing left vs right rotation
int stepsToNewTail = k; // This is for left rotation!
// ✓ CORRECT - Right rotation
int stepsToNewTail = length - k;
🎯 Pattern Recognition
Problem Type: Rotate List
Core Pattern: Make Circular + Break
When to Apply:
✓ Rotate array/list by k positions
✓ Circular rotation
✓ Move last k elements to front
✓ Shift elements
Recognition Keywords:
- "rotate"
- "rotate right/left"
- "shift"
- "circular"
- "move last k to front"
Similar Problems:
- Rotate Array (LC 189) - Array version
- Rotate String (LC 796) - String version
- Split Linked List in Parts (LC 725) - Circular concept
Key Components:
┌────────────────────────────────────────────┐
│ Find Length: Count nodes + save tail │
│ Make Circular: tail.next = head │
│ Optimize k: k = k % length │
│ Find New Tail: Move (length - k) steps │
│ Break Circle: new_head, new_tail.next=null│
│ Time: O(n), Space: O(1) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I see this is a rotation problem"
Step 2: "I'll make the list circular, then break at the right spot"
Step 3: "First optimize k using modulo"
Key Points to Mention:
- Circular list approach is cleanest
- Must optimize k with k % length
- Right rotation by k = new tail at (length - k)
- Two passes: find length/tail, find new tail
- Handle k = 0 case (break circle)
- Time: O(n), Space: O(1)
Walk Through Example:
"For [1,2,3,4,5], k=2:
Length is 5, tail is 5.
Make circular: 5 points to 1.
k = 2 % 5 = 2, so rotate by 2.
New tail at position 5-2=3, which is node 3.
New head is node 4.
Break after node 3.
Result: [4,5,1,2,3]"
Why Circular:
"Making it circular simplifies the logic.
Instead of finding old tail and reconnecting,
I just break at one position.
One clean operation instead of multiple steps."
Edge Cases to Mention:
✓ k = 0 → no rotation, but break circle!
✓ k > length → use k % length
✓ k = length → back to original
✓ Empty list → return null
✓ Single node → return as is
📝 Quick Revision Notes
🎯 Core Concept:
Rotate List: Make list circular (tail.next = head), find new tail at position (length - k), break circle (new_head = new_tail.next, new_tail.next = null). CRITICAL: Optimize k with k % length first! Don't forget to break circle even when k=0.
⚡ Quick Implementation:
import java.util.Arrays;
import java.util.List;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public static ListNode create(List<Integer> list) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
for(int num : list) {
curr.next = new ListNode(num);
curr = curr.next;
}
return dummy.next;
}
public static void print(ListNode head) {
ListNode curr = head;
while (curr != null) {
System.out.print(curr.val + " -> ");
curr = curr.next;
}
System.out.println();
}
public ListNode rotateRight(ListNode head, int k) {
// base case - number of nodes 0 or 1
if(head == null || head.next == null || k == 0) {
return head;
}
// Key approach - make the list circular by attaching head to tail.
ListNode curr = head;
int len = 1;
while (curr.next != null) {
curr = curr.next;
len++;
}
// Now curr is at last node. We made the list circular with the below.
curr.next = head;
// Finding the new head. Move head `len - k` steps forward.
k = k % len;
k = len - k;
ListNode temp = head;
while (k > 1) {
temp = temp.next;
k--;
}
ListNode newHead = temp.next; // initializing the new head
temp.next = null; // cutting the circle.
return newHead;
}
public static void main(String[] args) {
Solution t = new Solution();
ListNode list1 = create(Arrays.asList(1,2,3,4,5));
print(t.rotateRight(list1, 2));
print(t.rotateRight(create(Arrays.asList(0, 1, 2)), 4));
print(t.rotateRight(create(Arrays.asList()), 0));
print(t.rotateRight(create(Arrays.asList(1)), 0));
print(t.rotateRight(create(Arrays.asList(1)), 1));
print(t.rotateRight(create(Arrays.asList(1, 2)), 1));
}
}
🔑 Key Insights:
- Pattern: Circular + Break
- Optimize: k = k % length (critical!)
- New tail: At position (length - k)
- Circular: Simplifies reconnection
- Break: Even when k=0 after optimization
- Time: O(n), Space: O(1) ✓
🎪 Memory Aid:
"Circle it, find the cut, break and return!"
"Circular → Cut → Break!" ✨
⚠️ Critical Formula:
Right rotation by k:
New tail position = length - k
Why?
[1, 2, 3, 4, 5], k=2
Move last 2 to front
Last 2 start at position: 5-2+1 = 4
New tail is before that: position 3
Formula: length - k
Don't forget: k = k % length first!
🧪 Edge Cases
Case 1: Empty list
Input: head = null, k = 5
Output: null
Handled: Early return
Case 2: Single node
Input: head = [1], k = 99
Output: [1]
Handled: Early return
Case 3: k = 0
Input: head = [1,2,3], k = 0
Output: [1,2,3]
Handled: Break circle, return
Case 4: k = length
Input: head = [1,2,3], k = 3
Output: [1,2,3]
k % 3 = 0, no rotation
Case 5: k > length
Input: head = [1,2], k = 2000000000
Output: [1,2] (k % 2 = 0)
Handled: Modulo optimization
All handled perfectly! ✓
Related Problems
- Rotate Array (LC 189) - Array version, similar concept
- Rotate String (LC 796) - String rotation
- Reverse Linked List II (LC 92) - Partial operations
- Split Linked List in Parts (LC 725) - Circular concepts
Happy practicing! 🎯
Note: The circular list trick is a powerful technique! It simplifies many rotation and reconnection problems. The key insight is: k % length optimization prevents unnecessary work. Master this pattern and rotation problems become trivial! 💪✨