Given the head of a linked list and a non-negative integer k, rotate the list to the right by k places. One right rotation moves the last node to the front. Return the new head.
- 0 <= number of nodes <= 500
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10^9
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force moves the last node to the front k times. Each move needs a walk to the end, so it is O(n * k), hopeless for k = 2 * 10^9. Two observations fix it. First, rotating by n gives back the same list, so only k % n matters. Second, a rotation by k just means the last k nodes move to the front as a block: the new tail is node n - k (1-indexed) and the new head is the node after it. Closing the list into a ring and cutting at the right spot does this in one extra walk.
Algorithm
- If the list is empty or has one node, return it.
- Walk to the tail while counting the length
n. - Set
k = k % n; ifk == 0, return the head unchanged. - Link the tail to the head, then walk
n - ksteps from the tail to reach the new tail. - The new head is
newTail.next; setnewTail.next = nulland return the new head.
O(n)Space: O(1)k modulo the length before doing anything else, and handle the empty list first, otherwise k % 0 crashes. Interviewers often ask for the rotate left version as a follow-up: it is the same cut at position k % n.class Solution: def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: if not head or not head.next: return head # Find the length and the tail. n, tail = 1, head while tail.next: tail = tail.next n += 1 k %= n if k == 0: return head # Close the ring, then cut after node n - k. tail.next = head new_tail = tail for _ in range(n - k): new_tail = new_tail.next new_head = new_tail.next new_tail.next = None return new_head