Rotate List

• If head is null, head.next is null, or k is 0, return head.
• Calculate the length of the list, n.
• Calculate k = k % n. If k == 0, return head.
• Repeat k times:
  • Traverse to the end of the list to find the last node (last) and the second-to-last node (secondLast).
  • Set secondLast.next = null.
  • Set last.next = head.
  • Update head = last.
• Return head.

The core idea is to perform the rotation one step at a time. To rotate the list to the right by one, we need to move the last element to the front. This involves finding the last and second-to-last nodes, making the last node the new head, and adjusting the pointers accordingly. This entire process is repeated k times.

To avoid unnecessary rotations when k is larger than the list length n, we first compute the effective number of rotations as k' = k % n. If k' is 0, the list remains unchanged. Otherwise, we perform the single-step rotation k' times.

Here is the algorithm:

1. Handle edge cases: an empty list, a single-node list, or k=0.
2. Calculate the list's length, n.
3. Compute k = k % n. If k is 0, return the original list.
4. Loop k times: a. Find the last node and its predecessor (the second-to-last node). b. Set the next of the second-to-last node to null. c. Set the next of the last node to the current head. d. Update the head to be the last node.
5. Return the modified head.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode rotateRight(ListNode head, int k) {13        if (head == null || head.next == null || k == 0) {14            return head;15        }16 17        // Find the length of the list18        int n = 1;19        ListNode current = head;20        while (current.next != null) {21            current = current.next;22            n++;23        }24 25        // Calculate effective rotations26        k = k % n;27        if (k == 0) {28            return head;29        }30 31        // Rotate k times32        for (int i = 0; i < k; i++) {33            ListNode last = head;34            ListNode secondLast = null;35            while (last.next != null) {36                secondLast = last;37                last = last.next;38            }39            40            if (secondLast != null) {41                secondLast.next = null;42                last.next = head;43                head = last;44            }45        }46 47        return head;48    }49}

• Handle edge cases: if head is null, head.next is null, or k is 0, return head.
• Traverse the list to find its length n and the tail node.
• Calculate k = k % n. If k == 0, no rotation is needed, so return head.
• Make the list circular by setting tail.next = head.
• Calculate the position of the new tail: steps = n - k - 1.
• Traverse steps from the head to find the newTail node.
• The newHead is newTail.next.
• Break the circular link: newTail.next = null.
• Return newHead.

Instead of rotating one element at a time, we can solve this problem by rearranging pointers in a more direct way. The key insight is that rotating the list k times to the right is equivalent to taking the last k nodes and moving them to the front.

The steps are as follows:

1. First, traverse the list to find its length, n, and its tail node.
2. Handle edge cases: if the list is empty, has one node, or k is 0, return the head.
3. Calculate the effective rotations k = k % n. If k is 0, the list is unchanged, so we can return the head.
4. Make the list circular by connecting the next pointer of the tail node to the head node.
5. Now that we have a circular list, we need to find the new head and new tail. The last k nodes will form the new beginning of the list. This means the new tail is the node at position n - k - 1 (0-indexed) from the original head.
6. We traverse n - k - 1 steps from the head to locate the newTail.
7. The newHead is the node immediately following newTail.
8. To finalize the new list, we break the circular link by setting newTail.next to null.
9. Finally, we return the newHead.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode rotateRight(ListNode head, int k) {13        if (head == null || head.next == null || k == 0) {14            return head;15        }16 17        // 1. Find the length and the tail node18        int n = 1;19        ListNode tail = head;20        while (tail.next != null) {21            tail = tail.next;22            n++;23        }24 25        // Calculate effective rotations26        k = k % n;27        if (k == 0) {28            return head; // No rotation needed29        }30 31        // 2. Connect the tail to the head to form a circle32        tail.next = head;33 34        // 3. Find the new tail. It's at position (n - k - 1)35        int stepsToNewTail = n - k - 1;36        ListNode newTail = head;37        for (int i = 0; i < stepsToNewTail; i++) {38            newTail = newTail.next;39        }40 41        // 4. The new head is the node after the new tail42        ListNode newHead = newTail.next;43 44        // 5. Break the circle45        newTail.next = null;46 47        return newHead;48    }49}