Rotate List - Video Solutions

Problem Overview: Given the head of a singly linked list, rotate the list to the right by k positions. Nodes shifted past the end wrap around to the front. The challenge is performing this rotation efficiently without repeatedly traversing the list.

Approach 1: Convert to Circular List (Time: O(n), Space: O(1))

The key insight is that rotating a list is equivalent to breaking it at a specific position and reconnecting the ends. First traverse the linked list to compute its length n and locate the tail. Connect the tail back to the head to form a circular list. Since rotating by k where k > n repeats the same rotations, reduce it using k % n. The new tail becomes the n - (k % n) - 1 node from the start, and the next node becomes the new head. Break the circle at the new tail to restore a proper singly linked list.

This approach performs only two linear passes: one to compute length and another to locate the new tail. No extra data structures are required, making the space complexity constant.

Approach 2: Two-Pointer Technique (Time: O(n), Space: O(1))

This method uses the two pointers pattern to locate the rotation split point without explicitly forming a circular list first. Start by computing the length n and reduce rotations with k % n. Move a fast pointer k steps ahead of a slow pointer. Then advance both pointers together until the fast pointer reaches the last node.

At this point, the slow pointer sits at the node just before the new head. Detach the list after the slow pointer, set that next node as the new head, and connect the original tail to the old head. The rotation happens in a single pass after the length calculation.

The two-pointer approach is often preferred when you want a clear pointer movement strategy. It directly identifies the split point using pointer distance rather than temporarily modifying the structure.

Recommended for interviews: Both solutions run in O(n) time with O(1) space, which is the expected optimal complexity for this problem. Interviewers commonly expect the circular list trick because it simplifies the reasoning and reduces pointer edge cases. Demonstrating the two-pointer version shows strong control over pointer manipulation in linked list problems, which is a frequent interview theme.