61. Rotate List

Intuition

To rotate a linked list to the right by k places, we can think of the list as a circular structure. By connecting the tail to the head, the list becomes circular, and we can then break it at the appropriate position to simulate the rotation.

The idea is:

• Move the last k nodes to the front.

• But instead of manually detaching and reattaching nodes, we can use pointer arithmetic to find the new head efficiently.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N)$

Code

public ListNode rotateRight(ListNode head, int k) {
    // Edge case: if list is empty or no rotation needed
    if (k == 0 || head == null) return head;

    ListNode tailPointer = head;
    int length = 1;

    // Count number of nodes and find the last node
    while (tailPointer.next != null) {
        tailPointer = tailPointer.next;
        length++;
    }

    // If there's only one node, no rotation needed
    if (length == 1) return head;

    // Make the list circular
    tailPointer.next = head;

    // Find effective number of steps to rotate
    int stepsToNewHead = length - (k % length);

    ListNode previousToNewHead = tailPointer;
    // Move both head and previous pointer forward to locate new head
    while (stepsToNewHead > 0) {
        previousToNewHead = head;
        head = head.next;
        stepsToNewHead--;
    }

    // Break the loop to finalize the new list
    previousToNewHead.next = null;

    return head;
}