Given the head of a linked list, rotate the list to the right by k places.
Each rotation moves the last node to the front of the list.
Input: head = [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
Explanation: After 1 rotation: [5,1,2,3,4]. After 2 rotations: [4,5,1,2,3].
Input: head = [0, 1, 2], k = 4
Output: [2, 0, 1]
Explanation: k=4 is equivalent to k=1 (4 mod 3 = 1). After 1 rotation: [2,0,1].
The key insight is that rotating right by k is equivalent to cutting the list at position
n - (k mod n) from the start, where n is the length of the list.
We connect the tail to the head forming a ring, then break the ring at the right position.
- Find the length n of the list and the tail node.
- Compute the effective rotation: k = k % n. If k == 0, return head unchanged.
- Connect the tail to the head, making the list circular.
- Advance to the new tail position: n - k - 1 steps from the head.
- The new head is newTail.next. Set newTail.next = null to break the ring.
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class RotateList {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) return head;
// Step 1: Find length and tail
int n = 1;
ListNode tail = head;
while (tail.next != null) {
tail = tail.next;
n++;
}
// Step 2: Compute effective rotation
k = k % n;
if (k == 0) return head;
// Step 3: Connect tail to head (make circular)
tail.next = head;
// Step 4: Find new tail (n - k - 1 steps from head)
ListNode newTail = head;
for (int i = 0; i < n - k - 1; i++) {
newTail = newTail.next;
}
// Step 5: Break the ring at new tail
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}
Complexity Analysis:
Time complexity: O(n) where n is the length of the list. We traverse the list at most twice.
Space complexity: O(1) as only a constant number of pointers are used.