Rotate List

What the problem is asking

Given the head of a linked list, rotate the list to the right by k places.

That means the last k nodes should move to the front while the relative order of all nodes stays the same.

For example:

• head = [1, 2, 3, 4, 5], k = 2 becomes [4, 5, 1, 2, 3]
• head = [0, 1, 2], k = 4 becomes [2, 0, 1]

Intuition

To rotate a linked list to the right by k places, we need to move the last k nodes to the front.

Doing this one rotation at a time would be wasteful, especially because k can be very large. Instead, find the list length, reduce k with modulo, temporarily connect the tail to the head, and then break the circle at the new tail.

Pattern

Length + circular linked list + controlled break

Approach

First traverse the list to find:

• length, the total number of nodes
• tail, the last node

Then reduce unnecessary rotations:

k = k % length

If k becomes 0, the list already ends up in the same order.

Otherwise, connect the tail back to the head. Now the list is circular, so the rotated list is just a matter of choosing a new breaking point.

For a right rotation by k, the new tail is at position:

length - k

from the original head, using 1-based movement. The node after this new tail becomes the new head.

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

        int length = 1;
        ListNode tail = head;

        while (tail.next != null) {
            tail = tail.next;
            length++;
        }

        k %= length;
        if (k == 0) {
            return head;
        }

        tail.next = head;

        int stepsToNewTail = length - k;
        ListNode newTail = head;

        for (int i = 1; i < stepsToNewTail; i++) {
            newTail = newTail.next;
        }

        ListNode newHead = newTail.next;
        newTail.next = null;

        return newHead;
    }
}

Dry run

Take:

head = [1, 2, 3, 4, 5], k = 2

The length is 5, so:

k = 2 % 5 = 2

Now connect the tail to the head:

1 -> 2 -> 3 -> 4 -> 5 -> 1 -> ...

The new tail is after:

length - k = 5 - 2 = 3

steps from the original head, so the new tail is 3.

The node after 3 is 4, so 4 becomes the new head. Break the link after 3.

Final list:

4 -> 5 -> 1 -> 2 -> 3

Why modulo matters

If the list length is 3 and k = 4, rotating right 4 times is the same as rotating right once:

4 % 3 = 1

This prevents extra work and handles very large values of k.

Common mistakes

1. Moving nodes one by one

Rotating one step at a time costs O(n * k) in the worst case. Since k can be up to 2 * 10^9, that is not practical.

2. Forgetting to break the circle

After setting tail.next = head, the list becomes circular. Always set newTail.next = null after choosing the new head.

3. Using k directly

Always reduce k with modulo length. If k is equal to the length, or any multiple of it, the answer is the original list.

4. Off-by-one while finding the new tail

The new tail should be the (length - k)th node from the original head. Start from head and move steps - 1 times.

Complexity

Time Complexity: O(n)

We traverse the list once to find the length and tail, then move again to find the new tail.

Space Complexity: O(1)

The solution only rewires existing pointers and uses a few variables.