Rotate List - Video Solutions

Problem Overview: You are given the head of a singly linked list and an integer k. Rotate the list to the right by k positions. The last k nodes should move to the front while maintaining their relative order. The challenge is doing this without repeatedly traversing the list.

Approach 1: Convert to Circular List (O(n) time, O(1) space)

Traverse the linked list once to compute its length and keep a pointer to the tail. Connect the tail back to the head to form a circular list. Rotating right by k is equivalent to breaking the circle at position n - (k % n). Move a pointer to this new tail node, set newHead = newTail.next, and break the cycle by setting newTail.next = null. The key insight is reducing unnecessary rotations by using k % n, since rotating by the list length produces the same list. This method performs a constant number of passes and only changes pointers, making it efficient and easy to reason about.

Approach 2: Two-Pointer Technique (O(n) time, O(1) space)

This method uses the classic two pointers pattern. First compute the list length and reduce the rotation count using k % n. Move a fast pointer k steps ahead of the slow pointer. Then advance both pointers together until the fast pointer reaches the last node. At that moment, the slow pointer sits at the node right before the new head. Update pointers by setting newHead = slow.next, linking the current tail to the original head, and breaking the list at slow.next. This approach avoids forming an explicit cycle and instead finds the split point directly through pointer spacing.

Both techniques rely on careful pointer manipulation in a linked list. The main trick is recognizing that the effective rotation is k % n. Without that reduction, large values of k cause unnecessary work.

Recommended for interviews: Interviewers typically expect the O(n) solution with O(1) extra space. The circular list method is often considered the cleanest implementation because it directly models the rotation as a cycle and break operation. The two-pointer version demonstrates stronger control of pointer movement and is a good way to show mastery of two-pointer techniques. Either approach signals solid understanding of linked list manipulation.