AlgoScope

Rotate List

Close the list into a ring through the tail, then cut it n - k mod n steps in.

Linked list algorithms, algorithm, intermediate
Cut after 3.12345headcuttail
Cut after 3.12345headcuttail

Rewiring a List: Rotate right by 2

Decision, step 4 of 6

Walk n - k mod n - 1 = 5 - 2 - 1 = 2 steps from the head to 3: it becomes the new tail, and the node after it, 4, the new head.

How rewiring a list works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Taught by the same lesson

Rewiring a List covers these too, in the same run.