#61 Rotate List

frequently reported atBloomberg Amazon Microsoft

the problem

In plain words

Rotate a linked list to the right by k places: one rotation moves the last node to the front. k can be far larger than the length of the list.

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

out [4,5,1,2,3]

in head = [0,1,2], k = 4

out [2,0,1]

Rotating 3 times gives back [0,1,2]; one more gives [2,0,1].

0 ≤ number of nodes ≤ 500
-100 ≤ Node.val ≤ 100
0 ≤ k ≤ 2·10⁹

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternIn-place linked-list rewiring

Rotating n times changes nothing, so only k % n matters. Join the tail to the head to make a ring, then cut the ring open in the right place: the new tail is n − k − 1 hops from the old head.

solutions

From brute force to optimal

Do k % n single rotations; each walks to the second-to-last node and moves the last node to the front.

Count n; reduce k to k % n.
Repeat k times: walk to the second-to-last node, cut the last node off, put it in front.

timeO(n · (k mod n)), up to O(n²)

Each single rotation walks the whole list; there are up to n − 1 of them.

spaceO(1)

A few references.

javajava.util.*

1class Solution {2    public ListNode rotateRight(ListNode head, int k) {3        if (head == null || head.next == null) return head;4        int n = 0;5        for (ListNode p = head; p != null; p = p.next) n++;6        for (int r = 0; r < k % n; r++) {          // without % n, k = 2·10⁹ would never finish7            ListNode beforeLast = head;8            while (beforeLast.next.next != null) beforeLast = beforeLast.next; // walk to the 2nd-last node9            ListNode last = beforeLast.next;10            beforeLast.next = null;                // cut the last node off...11            last.next = head;                      // ...and put it in front12            head = last;13        }14        return head;15    }16}

Count n and find the tail in one pass; k %= n; tail.next = head; walk n − k − 1 steps to the new tail; cut after it.

Empty or one node → return head.
Walk to the tail counting n; k %= n; if k == 0 return head.
tail.next = head (a ring).
newTail = n − k − 1 hops from head; newHead = newTail.next; newTail.next = null.

timeO(n)

One pass to count, at most one more to reach the new tail.

spaceO(1)

A few references; nodes are re-linked, not copied.

javajava.util.*

1class Solution {2    public ListNode rotateRight(ListNode head, int k) {3        if (head == null || head.next == null) return head;4        int n = 1;5        ListNode tail = head;6        while (tail.next != null) {                // count the nodes and find the tail7            tail = tail.next;8            n++;9        }10        k %= n;                                    // rotating by n changes nothing11        if (k == 0) return head;12        tail.next = head;                          // close the list into a ring13        ListNode newTail = head;14        for (int i = 0; i < n - k - 1; i++) newTail = newTail.next; // n − k − 1 hops from head15        ListNode newHead = newTail.next;16        newTail.next = null;                       // cut the ring open at the new tail17        return newHead;18    }19}

in the room

How to say it in the interview

talk track

First say: "k can be 2·10⁹, so I'll reduce it with k % n — and that needs the length."
Counting the length also finds the tail — exactly what the ring needs.
Handle the empty list, one node, and k % n == 0 up front.

traps

Skipping k % n → up to 2·10⁹ rotations.
Computing k % n before checking for an empty list → ArithmeticException (division by zero).
Forgetting to cut the ring (newTail.next = null) → a list that never ends.

what they ask next

Follow-ups

Rotate left by k?

Rotating left by k is rotating right by (n − k % n) % n — reuse the same code.

Rotate an array instead (LC 189)?

Arrays can't be re-linked, so use three reversals: reverse all, then the first k, then the rest — O(n) time, O(1) space.

before you submit

Edge cases to test

Empty list → null (and avoid k % 0).
k = 0 or k a multiple of n → unchanged.
One node → unchanged for any k.
k = 2·10⁹ → only k % n matters.

practise next