Rotate List

This approach simulates the rotation process directly. We rotate the list to the right by one position and repeat this operation k times. A key optimization is to first calculate the effective number of rotations, k % n, where n is the length of the list, to handle large values of k.

• 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.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }

        // Find the length of the list
        int n = 1;
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
            n++;
        }

        // Calculate effective rotations
        k = k % n;
        if (k == 0) {
            return head;
        }

        // Rotate k times
        for (int i = 0; i < k; i++) {
            ListNode last = head;
            ListNode secondLast = null;
            while (last.next != null) {
                secondLast = last;
                last = last.next;
            }
            
            if (secondLast != null) {
                secondLast.next = null;
                last.next = head;
                head = last;
            }
        }

        return head;
    }
}