🚀 Introduction
The Rotate List problem is a classic linked list question frequently asked in coding interviews.
It tests your understanding of:
- linked list traversal
- pointer manipulation
- handling large constraints efficiently
👉 Try the problem yourself:
https://leetcode.com/problems/rotate-list/
🧠 Intuition
Rotating a list means shifting elements to the right.
Example:
1 → 2 → 3 → 4 → 5, k = 2
→ 4 → 5 → 1 → 2 → 3
Instead of rotating one by one, we can:
- either simulate using extra space
- or optimize using pointer manipulation
📘 Problem Explanation
You are given:
- Head of a linked list
- Integer
k
Return the list after rotating it k times to the right
🧩 Approach 1: Brute Force (Array-Based)
💡 Idea
- Store values in array
- Rotate indices
- rebuild linked list
💻 Java Code
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null) return head;
int count = 0;
ListNode curr= head;
while(curr != null){
count++;
curr = curr.next;
}
curr = head;
int[] arr = new int[count];
for(int i =0; i <count;i++){
arr[i] = curr.val;
curr = curr.next;
}
ListNode ans = new ListNode(-1);
ListNode finAns = ans;
k = k % count;
for(int i = 0;i < arr.length;i++){
int ind =(i+(count-k))%arr.length;
ans.next = new ListNode(arr[ind]);
ans = ans.next;
}
return finAns.next;
}
}
🔍 Dry Run (Brute Force)
Input:
[1,2,3,4,5], k = 2
Array:
[1,2,3,4,5]
After rotation logic:
[4,5,1,2,3]
Rebuild list → ✅ Final Answer
⏱️ Complexity
| Type | Value |
| Time | O(n) |
| Space | O(n) |
⚠️ Drawback
- Uses extra space
- Not optimal for large inputs
⚡ Approach 2: Optimal (Circular Linked List)
💡 Idea
Instead of rebuilding:
- convert list into circular
- break at correct position
💻 Java Code
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) return head;
int length = 1;
ListNode curr = head;
while (curr.next != null) {
curr = curr.next;
length++;
}
curr.next = head;
k = k % length;
int steps = length - k;
ListNode newTail = curr;
while (steps-- > 0) {
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}
🔍 Dry Run (Optimal)
Input: [1,2,3,4,5], k = 2
Length = 5
k = 2
Steps = 5 - 2 = 3
Move 3 steps → new tail = 3
new head = 4
Final:
4 → 5 → 1 → 2 → 3
⏱️ Complexity
| Type | Value |
| Time | O(n) |
| Space | O(1) |
📊 Comparison
| Approach | Time | Space | Best For |
| Array (Brute) | O(n) | O(n) | Beginners |
| Circular (Optimal) | O(n) | O(1) | Interviews |
📚 Related Problems
| Similar Pattern | Links |
| Reverse Linked List | Problem Link |
| Linked List Cycle | Problem Link |
| Remove Nth Node From End | Problem Link |
⚠️ Common Mistakes
- Forgetting
k % length - Incorrect pointer breaking
- Not handling single node
- Off-by-one in traversal
🎯 Key Points to Remember
- Always optimize k
- Use circular approach for best performance
- Understand pointer movement carefully
❓ FAQ
Q1: Why do we use k % length?
Because rotating more than length gives same result.
Q2: Which approach is better?
Optimal circular linked list approach.
Q3: Can we use array approach in interviews?
Yes, but optimal is preferred.
Q4: What is the key trick here?
Convert linked list into circular structure.
