Linked List Rotation

Description

Rotating a linked list by k places moves the last k nodes to the front, without moving any values. Join the tail to the head to make a ring, walk to the node that should become the new tail, and cut the ring after it. The whole skill is getting three numbers right: the length, k modulo the length, and how far from the head the cut falls.

We'll go from simple to more technical:

1. The pattern: measure, close the ring, cut at the new tail.
2. A second flavor: rotating left with the same steps and a different cut point.
3. Where "move the start, not the data" shows up (ring buffers).
4. The mistakes that rotate by the wrong amount or the wrong way.

The approach

Rotating doesn't need to move any values. Only the node where the list starts changes. So link the tail back to the head, making a ring. Then pick the node that should be the new tail, make the node after it the new head, and cut the ring there.

Rotating 6 -> 2 -> 9 -> 4 -> 7 right by 2:

The result is 4 -> 7 -> 6 -> 2 -> 9: the last two nodes moved to the front. Rotating by 7 gives the same list, because 7 % 5 is also 2.

if (head == null || head.next == null) return head;   // nothing to rotate
int length = 1;
ListNode tail = head;
while (tail.next != null) { tail = tail.next; length++; }

int shift = k % length;              // rotating by a multiple of the length is a no-op
if (shift == 0) return head;

tail.next = head;                     // temporarily circular
int stepsToNewTail = length - shift - 1;
ListNode newTail = head;
for (int i = 0; i < stepsToNewTail; i++) newTail = newTail.next;
ListNode newHead = newTail.next;
newTail.next = null;                  // break the circle at the new end
return newHead;

def rotate_right(head: ListNode | None, k: int) -> ListNode | None:
    if head is None or head.next is None:
        return head                          # nothing to rotate
    length = 1
    tail = head
    while tail.next is not None:
        tail = tail.next
        length += 1

    shift = k % length                       # rotating by a multiple of the length is a no-op
    if shift == 0:
        return head

    tail.next = head                         # temporarily circular
    new_tail = head
    for _ in range(length - shift - 1):
        new_tail = new_tail.next
    new_head = new_tail.next
    new_tail.next = None                     # break the circle at the new end
    return new_head

k % length isn't just a speed-up. Rotating by the full length gives back the same list. And the cut formula assumes the shift is between 0 and length - 1. With a raw k bigger than the length, length - k - 1 goes negative and the cut lands in the wrong place.

A second flavor: rotating the other direction

Rotating left by k moves the first k nodes to the end. The ring and the cut are the same. Only the new tail changes: it's shift - 1 steps from the head, counted from the front. Left by 2, the list above becomes 9 -> 4 -> 7 -> 6 -> 2.

tail.next = head;                          // temporarily circular, same as before
int stepsToNewTail = shift - 1;             // LEFT rotation: measured from the FRONT, not the back
ListNode newTail = head;
for (int i = 0; i < stepsToNewTail; i++) newTail = newTail.next;
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;

tail.next = head                             # temporarily circular, same as before
new_tail = head
for _ in range(shift - 1):                   # LEFT rotation: measured from the FRONT, not the back
    new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None

Mixing up the two formulas doesn't crash or make garbage. It gives a perfectly valid rotation in the other direction, so test with a direction you can check by hand.

Where you'll see it

A ring buffer works on the same idea. The data never moves; only the index where the sequence starts changes. Logs and queues with a fixed amount of memory are often built this way.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does shift = k % length matter beyond saving work?

2. For a right rotation, why is the new tail length - shift - 1 steps from the head, not shift steps?

3. A left rotation uses the right rotation's formula by mistake. What does it return?

Key takeaways

• Rotation moves where the list starts, not the values. A temporary ring turns it into choosing where to cut.
• Reduce k with k % length first, or the cut lands in the wrong place.
• Right rotation cuts length - shift - 1 steps from the head. Left rotation cuts shift - 1 steps from the head.
• Every bug here gives a believable list, so check the direction by hand.
• Relinking two pointers needs O(1) space. Copying the values into an array needs O(n).