How would you rotate a singly linked list to the right by k positions in place?

• A. Reverse entire list k times
• B. Find length n, set k = k mod n, detach the last k nodes and attach front; O(n)
• C. Move head to tail repeatedly k times; O(k)
• D. Create new list and copy nodes; O(n)

Answer: (B)

The key idea is to rotate in place by rewireing pointers so that the last k nodes move to the front without creating new nodes. To do this efficiently, you first measure the length of the list. Then normalize k with k mod n so you don’t rotate more than the length. If the result is zero, you can keep the list as is.

Next, locate the node just before the rotation point, which is the (n − k)th node. Cut the list after that node by setting its next to null. Keep a reference to the old head (which will become the tail’s next after the operation) and to the last node (the current tail). Connect the current tail’s next to the old head, and set the new head to the (n − k + 1)th node. This performs the rotation by rearranging existing pointers only, in O(n) time and O(1) extra space.

Why this works better than the other approaches: simply reversing the entire list would not yield a rotation. Moving the head to the tail one step at a time will produce the correct result but takes O(k) time, which can be inefficient if k is large. Creating a new list and copying nodes uses additional space and is not in place. The detach-and-attach method achieves the rotation with minimal passes and no extra storage.