61. Rotate List
You receive the head of a singly linked list and a non-negative integer k. Rotate the list to the right k times — each single rotation unhooks the last node and reattaches it at the front — and return the head of the rotated list.
After all rotations, the final k mod n nodes of the original list end up leading it (n is the list length). Note that k may be far larger than the list: rotating a list of length n exactly n times brings it back to where it started, so only k mod n moves actually matter.
An empty list rotates to itself.
Example 1:
Input: head = [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
Explanation: One rotation gives [5, 1, 2, 3, 4]; a second gives [4, 5, 1, 2, 3]. The last two nodes now lead the list.
Example 2:
Input: head = [0, 1, 2], k = 4
Output: [2, 0, 1]
Explanation: Rotating a 3-node list 4 times equals rotating it once (4 mod 3 = 1), so just the last node moves to the front.
Constraints:
- 0 ≤ number of nodes ≤ 500
- -1000 ≤ node value ≤ 1000
- 0 ≤ k ≤ 2 * 10⁹
Hints:
Rotating right by k is identical to rotating right by k mod n. Walk the list once to find n, and a huge k collapses to at most n - 1 real moves.
After computing n, the node that becomes the new tail sits n - (k mod n) - 1 hops from the head. Tie the old tail to the old head to form a ring, walk to that node, and cut the ring right after it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 2, 3, 4, 5], k = 2
Expected output: [4, 5, 1, 2, 3]