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: 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.
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.
C
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.
Time Complexity: O(n) because it requires traversal for counting.
Space Complexity: O(1) as no extra space is used.
First, we check whether the number of nodes in the linked list is less than 2. If so, we directly return head.
Otherwise, we first count the number of nodes n in the linked list, and then take the modulus of k by n to get the effective value of k.
If the effective value of k is 0, it means that the linked list does not need to be rotated, and we can directly return head.
Otherwise, we use fast and slow pointers, let the fast pointer move k steps first, and then let the fast and slow pointers move together until the fast pointer moves to the end of the linked list. At this time, the next node of the slow pointer is the new head node of the linked list.
Finally, we concatenate the linked list.
The time complexity is O(n), where n is the number of nodes in the linked list. The space complexity is O(1).
| 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.
|
| Fast and Slow Pointers + Link List Concatenation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert to Circular List | O(n) | O(1) | Best general solution. Simple logic and minimal pointer handling. |
| Two-Pointer Technique | O(n) | O(1) | Useful when applying fast/slow pointer patterns in linked list interview problems. |
Rotate List - Linked List - Leetcode 61 - Python • NeetCode • 58,825 views views
Watch 9 more video solutions →Practice Rotate List with our built-in code editor and test cases.
Practice on FleetCode