Rotate List: Circular Linked List Rotation

Rotate List is LeetCode 61. Given the head of a linked list, rotate the list to the right by k places.

Example: [1, 2, 3, 4, 5] with k = 2 becomes [4, 5, 1, 2, 3]. The last two nodes move to the front.

This problem looks like it requires shifting nodes one at a time, k times. That would work, but it would be slow. The key insight is that you do not need to rotate at all. You just need to find the right place to cut the list and reconnect the pieces.

The problem

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

• [1, 2, 3, 4, 5] with k = 2 produces [4, 5, 1, 2, 3]
• [0, 1, 2] with k = 4 produces [2, 0, 1]

Notice the second example: k = 4 is larger than the length of the list (3). Rotating a 3-node list by 3 gives you the original list back. So k = 4 is the same as k = 1. This is where modular arithmetic comes in.

The approach

The strategy is to temporarily make the list circular, then break it at the right position.

1. Find the length and the tail. Walk the entire list, counting nodes. When you reach the end, you have both the length n and a pointer to the tail node.
2. Compute effective rotation. Calculate k % n. If the result is 0, the list stays the same, so return early.
3. Connect tail to head. Set tail.next = head. The list is now a circular linked list.
4. Find the new tail. Starting from the current tail, walk forward n - k steps. The node you land on becomes the new tail of the result.
5. Break the circle. The new head is new_tail.next. Set new_tail.next = null to break the ring back into a normal linked list.

That is the entire algorithm. One traversal to find the length, one short walk to find the cut point, and a couple of pointer assignments.

Visual walkthrough

Let's trace through rotating [1, 2, 3, 4, 5] by k = 2.

The list goes from [1, 2, 3, 4, 5] to [4, 5, 1, 2, 3]. The last k nodes moved to the front, and the rest shifted to the back.

The solution

def rotateRight(head, k):
    if not head or not head.next or k == 0:
        return head

    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1

    k = k % length
    if k == 0:
        return head

    tail.next = head

    steps = length - k
    new_tail = tail
    for _ in range(steps):
        new_tail = new_tail.next

    new_head = new_tail.next
    new_tail.next = None
    return new_head

The code does exactly what the approach describes. Find the tail and length. Reduce k with modulo. Make it circular. Walk to the cut point. Break and return.

Complexity analysis

Time: O(n). You traverse the list once to find the length and tail (O(n)), then walk at most n more steps to find the cut point. That is O(n) total.

Space: O(1). Only a handful of pointer variables. No extra data structures.

The building blocks

This problem is built from two core building blocks:

Circular linked list technique. Connecting the tail to the head creates a ring. This lets you think about rotations as choosing a different starting point in the circle, rather than physically moving nodes around. The same idea appears any time you need to "wrap around" a linked list. By temporarily closing the loop, you turn a rotation problem into a cut-point problem.

Modular arithmetic for k. When k is larger than the list length, most of those rotations are wasted. A full rotation of n brings the list back to its original state. So k % n gives you the effective number of positions to rotate. Without this reduction, you would either loop forever or do unnecessary work. This is the same principle that shows up in array rotation problems and circular buffer indexing.

Edge cases

• Empty list. If head is None, return None immediately.
• k = 0. No rotation needed. Return head as-is.
• k larger than the length. Handled by k % length. For [0, 1, 2] with k = 4, the effective k is 4 % 3 = 1, producing [2, 0, 1].
• k equals the length. k % length = 0, so the list stays the same. The early return catches this.
• Single node. A list with one node cannot be rotated. The early return on not head.next handles it.

From understanding to recall

The idea behind this problem is clean: make it circular, find where to cut, and break it. You can probably explain that in ten seconds. But under pressure, the details trip you up. Which node do you start walking from? How many steps? Do you set new_tail.next to None or null?

The only way to lock this in is to type the solution from scratch, from memory, repeatedly. The first time you will probably get the step count wrong or forget the early return for k % length == 0. By the third or fourth rep, the five lines of pointer logic become automatic. That is when this problem stops costing you time in an interview.

Related posts

• Reverse Linked List - The fundamental pointer manipulation technique for linked lists
• Reorder List - Another linked list problem that combines multiple techniques into one solution