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 right by k means the last k nodes swing around to the front as a block, order preserved: [1,2,3,4,5] rotated by 2 becomes [4,5,1,2,3]. Nothing about the values changes — we are only choosing a new starting point and cutting the list there.

The naive rotation, and why k defeats it

The literal reading: rotate by one, k times. Each single rotation walks to the last node, moves it to the front, and repeats. That is O(N) per rotation, so O(k × N) overall — and k can be 2 × 10⁹, astronomically larger than the at-most-500 nodes. Almost all of that work is redundant: rotating a length-L list by L returns it to the start, so only k mod L rotations actually matter. Doing k of them is repeating the same cycle billions of times.

The reframe: close the list into a ring, then cut once

Rotation is not really about moving k nodes — it is about choosing where the list begins. Connect the tail back to the head and the list becomes a ring with no start and no end. On a ring, every node is a potential head; rotating is just deciding which one, then snapping the single link behind it to reopen the ring into a line. So instead of k moves we do exactly one cut — the whole cost of k collapses into finding the right place to snap.

Locating the cut

Reduce first: k %= length, because rotating by a full length changes nothing. To bring the last k nodes to the front, the new tail must be the node just before that block — the node at index length - k - 1 counting from the head (index 0). Its successor becomes the new head. We manage three roles: a scout that finds the old tail (and measures length on the way), the new tail (the breakpoint), and the new head.

python
if not head or not head.next or k == 0:
    return head

# 1. Measure length and reach the old tail
curr, length = head, 1
while curr.next:
    curr = curr.next
    length += 1
curr.next = head              # close the ring: old tail -> old head

# 2. Reduce k and locate the new tail
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 the ring open behind the new head
new_head = new_tail.next
new_tail.next = None
return new_head
Crucial Notereduce with k %= length before computing the cut, and only after you know the length. If k is a multiple of the length, k % length is 0, steps_to_new_tail is length - 1, the new tail is the old tail, and we snap exactly where the list already ended — returning it unchanged, which is correct. Skip the reduction and length - k - 1 goes wildly negative for large k, and the walk to the new tail is meaningless. Also note we must close the ring before cutting: it's what lets the last k nodes lead into the old head seamlessly.
Worked Example:[1, 2, 3, 4, 5], k = 2
- Measure: length 5, scout stops at node 5. Close ring: 5 → 1 (now 1→2→3→4→5→1→…).
- Reduce: k = 2 % 5 = 2. Steps to new tail = 5 − 2 − 1 = 2.
- Locate: from 1, take 2 steps: 1 → 2 → 3. new_tail = 3.
- Snap: new_head = 3.next = 4. Set 3.next = null.
- Result: 4 → 5 → 1 → 2 → 3 → null.
The cost, and the takeaway

One pass to measure, part of another to reach the cut: O(N) time, O(1) space — independent of k entirely, because k was reduced modulo the length. The reflex worth keeping: when an operation repeats a cyclic action k times and k can be huge, the answer is almost never "do it k times" — reduce k modulo the cycle length, or reframe the repetition as a single structural change (here, ring-and-cut). The same "wrap into a ring, snap once" idea reappears whenever rotation meets a circular structure.

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