Rotate List
Problem
Given the head of a linked list, rotate the list to the right by k places.
Walk to the tail to count the length n; close the list into a cycle by setting tail.next = head; advance n − (k mod n) steps from the head to find the new tail; cut the cycle there.
1 → 2 → 3 → 4 → 5, k = 24 → 5 → 1 → 2 → 3def rotate_right(head, k):
if not head or not head.next or k == 0: return head
n = 1; tail = head
while tail.next: tail = tail.next; n += 1
k %= n
if k == 0: return head
tail.next = head
new_tail = head
for _ in range(n - k - 1): new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_headfunction rotateRight(head, k) {
if (!head || !head.next || k === 0) return head;
let n = 1, tail = head;
while (tail.next) { tail = tail.next; n++; }
k %= n;
if (k === 0) return head;
tail.next = head;
let newTail = head;
for (let i = 0; i < n - k - 1; i++) newTail = newTail.next;
const newHead = newTail.next;
newTail.next = null;
return newHead;
}class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) return head;
int n = 1; ListNode tail = head;
while (tail.next != null) { tail = tail.next; n++; }
k %= n;
if (k == 0) return head;
tail.next = head;
ListNode newTail = head;
for (int i = 0; i < n - k - 1; i++) newTail = newTail.next;
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next || k == 0) return head;
int n = 1; ListNode* tail = head;
while (tail->next) { tail = tail->next; n++; }
k %= n;
if (k == 0) return head;
tail->next = head;
ListNode* newTail = head;
for (int i = 0; i < n - k - 1; i++) newTail = newTail->next;
ListNode* newHead = newTail->next;
newTail->next = nullptr;
return newHead;
}Explanation
Rotating a list to the right by k means the last k nodes jump to the front. Instead of shifting nodes one by one, we use a clever shortcut: turn the list into a circle and then snip it open at the right spot.
First we walk to the tail to count the length n. Since rotating by n brings the list back to itself, only k % n matters; if that is 0 the list is unchanged and we return early.
Next we join the tail to the head with tail.next = head, forming a loop. The new tail of the rotated list is n - k - 1 steps from the original head, so we walk that many steps to reach it.
The node right after that new tail becomes the new head. We cut the loop by setting new_tail.next = None and return the new head.
Example: 1→2→3→4→5 with k=2. Here n=5, so we walk 5-2-1 = 2 steps from the head to land on 3 (the new tail). We cut after it, making 4 the new head: 4→5→1→2→3.