Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4 Output: [2,0,1]
Constraints:
[0, 500].-100 <= Node.val <= 1000 <= k <= 2 * 109Problem 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.
This approach involves converting the linked list into a circular list and then breaking it at the correct point to achieve the required rotation.
By making the linked list a circular one, you can easily traverse k nodes from the end to set the new head and make necessary detachments.
In this solution, we first determine the length of the list and then make it circular. We perform a modulus operation on k to handle cases where k is greater than the length, effectively making unnecessary additional full rotations. Finally, we iterate over the circular list to the correct point to form a valid, rotated list, detaching the circle.
Java
Python
JavaScript
Time Complexity: O(n) because we pass through the list twice, once to find the length and once to find the new head.
Space Complexity: O(1) since we only use a constant amount of extra space.
In this approach, we utilize a two-pointer technique. We advance one pointer ahead by k nodes and then move another pointer from the start concurrently until the first pointer reaches the list's end. This way, the second pointer will eventually land on the node that will become the new tail.
This C++ solution starts by counting the length and linking the last node to the head to form a loop. It then uses two pointers: a fast pointer that traverses k nodes firstly and a slow pointer that starts from the head. Then moving both forward will find the new head when the fast pointer completes the loop.
Python
C#
Time Complexity: O(n) because it requires traversal for counting.
Space Complexity: O(1) as no extra space is used.
| Approach | Complexity |
|---|---|
| Approach 1: Convert to Circular List | Time Complexity: O(n) because we pass through the list twice, once to find the length and once to find the new head. |
| Approach 2: Two-Pointer Technique | Time Complexity: O(n) because it requires traversal for counting.
|
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert to Circular List | O(n) | O(1) | Clean and intuitive rotation logic. Good when pointer rewiring is acceptable. |
| Two-Pointer Technique | O(n) | O(1) | Preferred when you want to directly locate the split point using pointer distance. |
This Algorithm is SUPER HELPFUL for Coding Interviews! | Fast & Slow Pointers for Linked Lists • Greg Hogg • 225,888 views views
Watch 9 more video solutions →Practice Rotate List with our built-in code editor and test cases.
Practice on FleetCode