Rotate a Linked List to the Right
Solve this Problemk, rotate the list to the right by k places and return the new head.
Rotating by the list's full length brings it back to where it started, so only k mod n actually changes anything — the optimal solution leans on that by briefly making the list circularTemporary Circular LinkLinking the tail back to the head turns "wrap around to the front" into an ordinary next-pointer walk — no special-casing needed for indices that would otherwise fall off the end. The list is cut back into a normal (acyclic) one before returning.: link the tail back to the head, walk to exactly where the new tail belongs, and cut the circle there. The next node after that cut — found correctly even when it wraps around past the original last node — becomes the new head.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in head ≤ 500 - ◆
-1000 ≤ node value ≤ 1000 - ◆
0 ≤ k ≤ 2 × 10⁹
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node rotateRight(Node head, int k) { |
| 3 | if (head == null || head.next == null) { |
| 4 | return head; |
| 5 | } |
| 6 | int n = 1; |
| 7 | Node tail = head; |
| 8 | while (tail.next != null) { |
| 9 | tail = tail.next; |
| 10 | n++; |
| 11 | } |
| 12 | tail.next = head; |
| 13 | int stepsToNewTail = n - (k % n) - 1; |
| 14 | Node newTail = head; |
| 15 | for (int i = 0; i < stepsToNewTail; i++) { |
| 16 | newTail = newTail.next; |
| 17 | } |
| 18 | Node newHead = newTail.next; |
| 19 | newTail.next = null; |
| 20 | return newHead; |
| 21 | } |
| 22 | } |
| 23 |
1More than one node — rotation actually needs to happen.
Approach & Solutions
Brute Force — Rotate One Step at a Time, k mod n Times
GoodRotating by the full length n is the same as not rotating at all, so only k mod n single-step rotations actually matter. Perform that many single rotations, one at a time: each one walks to the second-to-last node, detaches the last node, and reattaches it at the front. Correct, but every single rotation costs its own O(n) walk to find the tail — the optimal solution finds the tail once and cuts the list in exactly the right place in a single pass.
O(n · (k mod n))O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node rotateRight(Node head, int k) {
9 if (head == null || head.next == null) {
10 return head;
11 }
12 int n = 0;
13 Node curr = head;
14 while (curr != null) {
15 n++;
16 curr = curr.next;
17 }
18 int steps = k % n;
19 for (int s = 0; s < steps; s++) {
20 Node secondLast = head;
21 while (secondLast.next.next != null) {
22 secondLast = secondLast.next;
23 }
24 Node last = secondLast.next;
25 secondLast.next = null;
26 last.next = head;
27 head = last;
28 }
29 return head;
30 }
31}Optimal — Make It Circular, Then Break at the Right Point
OptimalFind the real tail (counting the length for free along the way), and link it back to head — the list is now circular, so "wrap around to the front" is no longer a special case. The new tail sits n - (k mod n) - 1 steps from head; walk there, and its next node (found through the circular link, even if it wraps past the old end) becomes the new head. Cut the new tail's next pointer back to null, and the rotation is done in a single pass with no repeated walks.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node rotateRight(Node head, int k) {
9 if (head == null || head.next == null) {
10 return head;
11 }
12 int n = 1;
13 Node tail = head;
14 while (tail.next != null) {
15 tail = tail.next;
16 n++;
17 }
18 tail.next = head;
19 int stepsToNewTail = n - (k % n) - 1;
20 Node newTail = head;
21 for (int i = 0; i < stepsToNewTail; i++) {
22 newTail = newTail.next;
23 }
24 Node newHead = newTail.next;
25 newTail.next = null;
26 return newHead;
27 }
28}