Rotate List

Intuition

A right rotation only changes where the list starts and ends, not the relative order of the nodes. If we temporarily connect the tail back to the head, we get a circle where any node can serve as the head. Rotating right by k means the new head is the node sitting k positions from the end, which is the same as position length minus k from the front. Reducing k modulo the length avoids pointless full loops. Once we walk to the node just before the new head, we snap the ring there and hand back the new head.

Algorithm walkthrough

1. 1Handle trivial cases: an empty list, a single node, or k equal to zero returns head unchanged.
2. 2Traverse to the tail while counting nodes to get the length, then reduce k with k %= length.
3. 3If k becomes zero the list is unchanged, so return head; otherwise connect tail.next to head to form a ring.
4. 4Walk length - k - 1 steps from head to reach the node that will become the new tail.
5. 5Record newTail.next as the new head, cut the ring by setting newTail.next to null, and return the new head.

Implementation

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None or head.next is None or k == 0:
            return head
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1
        k %= length
        if k == 0:
            return head
        tail.next = head
        steps_to_new_tail = length - k - 1
        new_tail = head
        for _ in range(steps_to_new_tail):
            new_tail = new_tail.next
        new_head = new_tail.next
        new_tail.next = None
        return new_head