Algorithm

Rotate List

Linked List Pattern

Rotate List

Given the head of a linked list, rotate it to the right by k places and return the new head. Rotating right by 1 moves the last node to the front; rotating by k moves the last k nodes to the front as a block, preserving their order. k can be far larger than the list length. Rewire in place. An empty or single-node list, and any k that is a multiple of the length, returns the list unchanged.

CONSTRAINTS
  • The number of nodes is in the range [0, 500]
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 × 10⁹
EXAMPLE 1
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
The last two nodes (4, 5) move to the front as a block, keeping their order, and the rest follow.
EXAMPLE 2
Input: head = [0,1,2], k = 4
Output: [2,0,1]
With length 3, rotating by 4 is the same as rotating by 4 mod 3 = 1, so only the last node (2) moves to the front.
EXAMPLE 3
Input: head = [1,2,3], k = 3
Output: [1,2,3]
k equals the length, so a full rotation returns to the starting arrangement — the list is unchanged.
What if k is 0 or a multiple of the length?
k mod length is 0, meaning a whole number of full turns, so the list comes back to its original order and is returned unchanged.
Why can k be so much larger than the list?
Because rotating by the length is a no-op, only k mod length matters. Reducing k first is what keeps the work O(N) regardless of how large k is stated to be.
Is it right vs left rotation — does the direction matter?
This is rotation to the right (last nodes move to front). A left rotation by k is the same as a right rotation by length − k, so the ring approach handles either with a different cut index.
Do I need to handle the empty or single-node list specially?
Guard them up front: with zero or one node there is nothing to rotate, so return the head immediately before measuring.

Rotating a linked list to the right by k places means the last k nodes move to the front, while their relative order remains unchanged. Essentially, we are picking a new starting point and severing the link that previously made the list linear.

A naive approach would be to perform k individual rotations. For each rotation, we find the second-to-last node, make the last node point to the current head, and then make the second-to-last node point to null. If k is very large (e.g., 2 billion), this approach is extremely inefficient (O(k * N)). We need a way to perform the rotation in a single pass regardless of k.

Instead of moving nodes one-by-one, we can think of the rotation as a single "cut" in a circle. If we connect the tail of the list back to the head, we create a Ring. In a ring, there is no beginning or end—we can choose any node to be the new head. Once we find our target, we simply "snap" the link behind it to turn the ring back into a linear list.

To locate the exact spot to "snap" the ring, we use the formula L - k - 1. Here is why: if we want to move the last k nodes to the front, the new tail must be the node that sits just before those k nodes. In a list of length L, the last k nodes start at position (L - k + 1). Therefore, the new tail is at position (L - k). Since we start our traversal at the head (index 0), we need to take (L - k - 1) steps to reach that new tail.

To perform this surgery, we manage three pointers: the Tail (scout that finds the end), the New Tail (the breakpoint), and the New Head (the new starting point).

python
# 1. Measure and Circle
curr, length = head, 1
while curr.next:
    curr = curr.next
    length += 1
curr.next = head # Ring created

# 2. Locate Cut (using L - k - 1 steps)
k %= length
steps_to_new_tail = length - k - 1
new_tail = head
for _ in range(steps_to_new_tail):
    new_tail = new_tail.next

# 3. Snap
new_head = new_tail.next
new_tail.next = None
return new_head
Worked Example:[1, 2, 3, 4, 5], k=2
1
→
2
→
3
→
4
→
5
→
⟲ back to idx 0
We measure the list length (5) and connect the tail node 5 to the head node 1, creating a circular ring.
1
→
2
→
3
new_tail
→
4
→
5
→
⟲ back to idx 0
We calculate steps to new tail (5 - 2 - 1 = 2 steps). We start at head and move to index 2 (node 3), our new tail.
4
→
5
→
1
→
2
→
3
→
NULL
We establish node 4 (new_tail.next) as the new head, and sever the connection after node 3 by setting 3's next to null.
Interactive Strategy Visualization
CYCLED ROTATION ENGINE

Ring Persistence Manipulation

1
2
3
4
5
N=5, k=2 → Rot=2

Phase Details

Phase 1: Measure & Modulo

Traverse the list to find length N. Compute effective rotation: `k = k % N`. If `k=0`, we stop.

Math Hint

We use k = k % length because rotating a list of length 5 by 7 steps is the same as rotating it by 2 steps.

Strategy: The Circular Linked Hack

Time Complexity: O(N) | Space Complexity: O(1). Converting to a circle simplifies complex head/tail shuffling.

O(k × N) Repeated Rotation
→
O(N) Time · O(1) Space Ring-and-Cut