Skip to content

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;
}

Comments