Rotate List

Given the head of a linked list, rotate the list to the right by k places. Each rotation moves the last node to the front of the list.

Example 1

Input: head = [1, 2, 3, 4, 5], k = 2 Output: [4, 5, 1, 2, 3] Explanation: After 1 rotation: [5,1,2,3,4]. After 2 rotations: [4,5,1,2,3].

Example 2

Input: head = [0, 1, 2], k = 4 Output: [2, 0, 1] Explanation: k=4 is equivalent to k=1 (4 mod 3 = 1). After 1 rotation: [2,0,1].

Solution Approach - Form a Ring

The key insight is that rotating right by k is equivalent to cutting the list at position n - (k mod n) from the start, where n is the length of the list. We connect the tail to the head forming a ring, then break the ring at the right position.

Find the length n of the list and the tail node.
Compute the effective rotation: k = k % n. If k == 0, return head unchanged.
Connect the tail to the head, making the list circular.
Advance to the new tail position: n - k - 1 steps from the head.
The new head is newTail.next. Set newTail.next = null to break the ring.

Java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class RotateList {

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;

        // Step 1: Find length and tail
        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }

        // Step 2: Compute effective rotation
        k = k % n;
        if (k == 0) return head;

        // Step 3: Connect tail to head (make circular)
        tail.next = head;

        // Step 4: Find new tail (n - k - 1 steps from head)
        ListNode newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail.next;
        }

        // Step 5: Break the ring at new tail
        ListNode newHead = newTail.next;
        newTail.next = null;

        return newHead;
    }
}

Complexity Analysis:

Time complexity: O(n) where n is the length of the list. We traverse the list at most twice.
Space complexity: O(1) as only a constant number of pointers are used.