Definition
- Rotate right – move the last k nodes of a singly linked list to the front.
- Ring formation – connect the tail to the head, creating a circular list.
- Modulo reduction –
k = k % lengthhandles rotations larger than the list. - Cut point – the new tail is at position
length - kfrom the original head; the new head is the next node. - Complexity – O(n) time for one full walk plus a partial walk, O(1) space.
The National Bank of India keeps a circular roster of on-call settlement staff. Rotating the roster right by k means the last k staff move to the front. The clerk joins the ends into a loop, counts to the new cut point, and snips the loop so the list starts at the new front.
Understanding the Concepts
What is the Rotate LinkedList problem?
Given the head of a singly linked list and a non-negative integer k, rotate the list to the right by k places. This means the last k nodes move to the front. For example, rotating 1->2->3->4->5 right by 2 gives 4->5->1->2->3.
package com.bank.service;
public class RotateLinkedList {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) return head;
// Find length and tail
int length = 1;
ListNode tail = head;
while (tail.next != null) {
tail = tail.next;
length++;
}
// Reduce k
k = k % length;
if (k == 0) return head;
// Form ring
tail.next = head;
// Walk to new tail: (length - k) steps from head
ListNode newTail = head;
for (int i = 1; i < length - k; i++) {
newTail = newTail.next;
}
// Cut
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
Why form a ring?
Forming a ring by connecting the tail to the head simplifies the operation. Instead of detaching and reattaching two separate segments (error-prone with pointer management), we have a single circular list and just need to find where to cut. One cut gives us the rotated list.
// Without ring: need to manage 4 pointers
// prevNewHead.next = null (new tail)
// tail.next = head (reconnect)
// newHead = prevNewHead.next (save before cutting)
// With ring: form loop, find cut point, cut once
tail.next = head; // ring
// walk to new tail
newTail.next = null; // cut
Why use k % length?
Rotating by the full length returns the original list. Any k larger than the length is equivalent to k % length rotations. This also handles the case where k is 0 or a multiple of the length, where we return the original head without modification.
package com.bank.service;
public class ModuloDemo {
public static void main(String[] args) {
int length = 5;
System.out.println("k=2: effective = " + (2 % length)); // 2
System.out.println("k=7: effective = " + (7 % length)); // 2
System.out.println("k=5: effective = " + (5 % length)); // 0 (no-op)
System.out.println("k=0: effective = " + (0 % length)); // 0 (no-op)
}
}
k=2: effective = 2
k=7: effective = 2
k=5: effective = 0
k=0: effective = 0
How do you find the cut point?
The new tail is at position (length - k) from the original head. We walk (length - k - 1) steps from the head to reach the new tail. The node after it becomes the new head.
package com.bank.service;
public class CutPointDemo {
public static void main(String[] args) {
// List: 1->2->3->4->5, k=2, length=5
// New tail at position: 5 - 2 = 3 (1-indexed)
// Walk 2 steps from head: head(1)->2->3
// New tail = node 3, new head = node 4
// Result: 4->5->1->2->3
System.out.println("Cut after position " + (5 - 2) + " from head");
System.out.println("Walk " + (5 - 2 - 1) + " steps from head");
}
}
Cut after position 3 from head
Walk 2 steps from head
What are the edge cases?
Edge cases include an empty list, a single-node list, k equal to zero, and k being a multiple of the list length. All of these return the original head unchanged.
package com.bank.service;
public class RotateEdgeCases {
public static void main(String[] args) {
RotateLinkedList solver = new RotateLinkedList();
// Empty list
System.out.println(solver.rotateRight(null, 3)); // null
// Single node
ListNode single = new ListNode(1);
System.out.println(solver.rotateRight(single, 5).val); // 1
// k = 0
ListNode list = new ListNode(1);
list.next = new ListNode(2);
System.out.println(solver.rotateRight(list, 0).val); // 1
}
}
null
1
1
What are common mistakes?
The most common mistake is trying to detach and reattach two segments manually without forming a ring, leading to pointer errors. Another mistake is forgetting the modulo step, causing the algorithm to walk past the end of the list for large k values.
// WRONG: no modulo, k=1000000 on a 5-node list
for (int i = 0; i < k; i++) { /* walks 1000000 steps! */ }
// CORRECT: reduce k first
k = k % length; // now at most length-1 steps
How is this different from rotating an array?
Array rotation uses the reverse-three-times trick (reverse whole, reverse first k, reverse rest) because random access is available. Linked list rotation uses the ring-and-cut approach because we can only traverse sequentially.
| Aspect | Array Rotation | LinkedList Rotation |
|---|---|---|
| Access | Random (index-based) | Sequential (pointer-based) |
| Strategy | Reverse three times | Form ring, cut |
| Extra space | O(1) (in-place reversal) | O(1) (pointer manipulation) |
| Time | O(n) | O(n) |
// Array: reverse-three-times
reverse(arr, 0, n - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, n - 1);
// LinkedList: ring and cut
tail.next = head;
// walk to new tail, cut
How would you apply this in a banking system?
At the National Bank of India, a daily on-call roster of settlement staff is stored as a linked list. Each day the roster rotates right by k positions so the last k staff cycle to the front. The ring-and-cut approach rotates the roster in place with no extra memory.
package com.bank.service;
public class OnCallRosterService {
public ListNode rotateRoster(ListNode roster, int daysRotation) {
if (roster == null || roster.next == null || daysRotation == 0)
return roster;
int length = 1;
ListNode tail = roster;
while (tail.next != null) { tail = tail.next; length++; }
daysRotation = daysRotation % length;
if (daysRotation == 0) return roster;
tail.next = roster;
ListNode newTail = roster;
for (int i = 1; i < length - daysRotation; i++)
newTail = newTail.next;
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}
What should a senior engineer know?
A senior engineer should know that forming a ring is cleaner than manual segment management. They should also recognise that rotating left by k is the same as rotating right by (length - k), so one implementation handles both directions. The ring-and-cut pattern also applies to other cyclic list problems.
// Rotate left by k = Rotate right by (length - k)
// public ListNode rotateLeft(ListNode head, int k) {
// return rotateRight(head, length - k);
// }
// The ring-and-cut pattern is reusable:
// 1. Find length and tail
// 2. Form ring
// 3. Walk to cut point
// 4. Cut and return new head
Visual Overview
Original: 1 → 2 → 3 → 4 → 5, k=2 Step 1: Find length=5, tail=5 1 → 2 → 3 → 4 → 5 → null Step 2: k = 2 % 5 = 2 Step 3: Form ring (tail.next = head) 1 → 2 → 3 → 4 → 5 ─┐ ↑ │ └─────────────────────┘ Step 4: Walk to new tail: length - k = 3 Walk 2 steps from head: 1 → 2 → 3 (new tail) New head = 3.next = 4 Step 5: Cut (newTail.next = null) 4 → 5 → 1 → 2 → 3 → null Result: 4 → 5 → 1 → 2 → 3
Key Takeaway
Rotating a singly linked list right by k places is cleanest when I first turn the list into a ring. I walk the list once to find both its length and its tail, then connect the tail back to the head. The crucial step is reducing k by the length with modulo, because rotating by a full length returns the original list.
With the effective rotation known, the new tail sits at position (length - k) from the original head. I walk to that node, set the node after it as the new head, and break the ring by setting the new tail's next to null. Forming the ring and cutting once is far less error-prone than manually detaching and reattaching two segments.
Edge cases include empty lists, single-node lists, and k being zero or a multiple of the length. All return the original head unchanged. The algorithm runs in O(n) time and O(1) space.
At the National Bank of India, this drove a daily on-call roster rotation. Settlement staff were stored as a linked chain, and each day the roster rotated right by k positions so staff at the end cycled to the front to balance the workload fairly.
Remember one sentence: form a ring, reduce k by length, cut at position length minus k, and the node after the cut is the new head.
---