Medium · Cycle then Break
Understand → Visualise → Practice.
Return the traversal after rotating a linked list right by k positions.
Rotating right by k moves the last k nodes to the front. Link the tail to the head to form a ring, then cut it n − (k mod n) nodes from the old head.
Walk once to count n nodes and reach the tail.
k = k mod n; if it is 0, the list is unchanged.
Connect tail to head, walk n − k − 1 steps to the new tail, and make its next node the new head.
O(n) time and O(1) extra space.
Rotating one step at a time costs O(n × k), and k may be much larger than n.
Read the full guide first: Linked Lists.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.