DSA problem
Rotate List
Given the head of a linked list, rotate the list to the right by k places. Rotating to the right by one place means the last node moves to the front and every other node shifts one position toward the tail.
The first subtlety is that k may be much larger than the list length n. Rotating by n places returns the original list, so the effective number of rotations is k mod n. If this remainder is zero, the list is unchanged.
A second observation simplifies the rewiring: rotating to the right by k is equivalent to making a new break in the list. The new head becomes the node at position n - (k mod n) from the start, and the node just before it becomes the new tail.
The intuition is to first walk the list to count its length and find the old tail. Connect that tail back to the head, forming a temporary ring. Then advance n - (k mod n) steps from the head to locate the new tail, set the new head as its successor, and finally break the ring by setting the new tail's next to null. This solves the problem in a single conceptual pass with constant extra space.
Examples
head = [1,2,3,4,5], k = 2[4,5,1,2,3]head = [0,1,2], k = 4[2,0,1]head = [1,2], k = 0[1,2]Constraints
- The number of nodes in the list is in the range [0, 500].
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.