Problem Description

You are given the head of a singly linked list and an integer k. Your task is to rotate the list to the right by k places.

Rotating a linked list to the right by k places means:

• Take the last k nodes from the end of the list
• Move them to the beginning of the list
• Maintain the relative order of all nodes

For example, if you have a linked list 1 -> 2 -> 3 -> 4 -> 5 and k = 2:

• The last 2 nodes are 4 -> 5
• After rotation, the list becomes 4 -> 5 -> 1 -> 2 -> 3

The solution handles several important cases:

1. If the list is empty or has only one node, no rotation is possible, so it returns the original head
2. Since rotating by the length of the list results in the same list, the algorithm uses k % n where n is the length of the list to avoid unnecessary rotations
3. If k % n = 0, no rotation is needed

The algorithm uses a two-pointer technique:

• First, it counts the total number of nodes n in the list
• It calculates the effective rotation amount as k % n
• A fast pointer moves k steps ahead of a slow pointer
• Both pointers then move together until the fast pointer reaches the last node
• At this point, the slow pointer is at the node just before the rotation point
• The list is then split and reconnected: the part after the slow pointer becomes the new beginning, and the original beginning connects to where the fast pointer ended

Intuition

The key insight is recognizing that rotating a linked list to the right by k positions is equivalent to taking the last k nodes and moving them to the front. But how do we find these last k nodes efficiently in a singly linked list where we can only traverse forward?

First, we need to handle the edge case where k might be larger than the list length. If we have 5 nodes and need to rotate by 7, that's the same as rotating by 7 % 5 = 2. This is because rotating by the list length brings us back to the original configuration.

To find the split point without traversing the list multiple times, we can use the two-pointer technique. If we need to rotate by k positions, we need to find the (n-k)th node from the beginning, which will become the last node of our rotated list.

Here's the clever part: instead of calculating n-k and then traversing to that position, we can use two pointers with a gap of k between them. We start by moving the fast pointer k steps ahead. Then, when we move both pointers together until the fast pointer reaches the end, the slow pointer will naturally be at position n-k - exactly where we need to split the list.

Why does this work? When the fast pointer has traveled n nodes total (reaching the end), the slow pointer has traveled n-k nodes, positioning it right before the rotation point. The node after the slow pointer (slow.next) becomes our new head, and we reconnect the original tail to the original head to complete the rotation.

This approach elegantly solves the problem in just two passes through the list: one to count the nodes and calculate k % n, and another to find the split point and perform the rotation.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

The implementation uses the fast and slow pointer technique combined with linked list manipulation. Let's walk through the solution step by step:

Step 1: Handle Edge Cases

if head is None or head.next is None:
    return head

If the list is empty or has only one node, no rotation is possible, so we return the original head.

Step 2: Count the Number of Nodes

cur, n = head, 0
while cur:
    n += 1
    cur = cur.next

We traverse the entire list once to count the total number of nodes n. This is necessary to handle cases where k > n.

Step 3: Calculate Effective Rotation

k %= n
if k == 0:
    return head

Since rotating by n positions brings the list back to its original state, we use modulo operation k %= n to get the effective rotation amount. If k becomes 0, no rotation is needed.

Step 4: Set Up Two Pointers with Gap

fast = slow = head
for _ in range(k):
    fast = fast.next

Initialize both pointers at the head, then advance the fast pointer by k positions. This creates a gap of k nodes between the fast and slow pointers.

Step 5: Move Both Pointers Until Fast Reaches the End

while fast.next:
    fast, slow = fast.next, slow.next

Move both pointers simultaneously until the fast pointer reaches the last node (when fast.next is None). At this point, the slow pointer is at the (n-k)th node, which is the node just before the rotation point.

Step 6: Perform the Rotation

ans = slow.next        # New head is the node after slow
slow.next = None       # Break the link to split the list
fast.next = head       # Connect the tail to the original head
return ans             # Return the new head

The rotation is achieved by:

• Saving the new head (slow.next)
• Breaking the link after the slow pointer to split the list into two parts
• Connecting the tail of the second part (where fast is) to the original head
• Returning the new head

This approach efficiently rotates the list in O(n) time with only two passes through the list and uses O(1) extra space.

Example Walkthrough

Let's walk through the solution with a concrete example: rotating the linked list 1 -> 2 -> 3 -> 4 -> 5 by k = 2 positions to the right.

Initial State:

head -> 1 -> 2 -> 3 -> 4 -> 5 -> None
k = 2

Step 1: Handle Edge Cases The list has more than one node, so we continue.

Step 2: Count Nodes Traverse the list to count nodes:

n = 5

Step 3: Calculate Effective Rotation

k = k % n = 2 % 5 = 2

Since k ≠ 0, we proceed with rotation.

Step 4: Create Gap Between Pointers Initialize both pointers at head, then move fast pointer 2 steps ahead:

Initial:  slow -> 1 -> 2 -> 3 -> 4 -> 5
          fast -> 1 -> 2 -> 3 -> 4 -> 5

After moving fast by k=2:
          slow -> 1 -> 2 -> 3 -> 4 -> 5
                        fast -> 3 -> 4 -> 5

Step 5: Move Both Pointers Together Move both pointers until fast reaches the last node:

First move:
          slow -> 2 -> 3 -> 4 -> 5
                        fast -> 4 -> 5

Second move:
          slow -> 3 -> 4 -> 5
                        fast -> 5 -> None

Now fast is at the last node (5), and slow is at node 3.

Step 6: Perform Rotation

1. ans = slow.next = 4  (node 4 becomes new head)
2. slow.next = None     (break link: 3 -> None)
3. fast.next = head     (connect 5 -> 1)

Final Result:

Before: 1 -> 2 -> 3 -> 4 -> 5 -> None
After:  4 -> 5 -> 1 -> 2 -> 3 -> None

The last 2 nodes (4 and 5) have been moved to the front while maintaining their relative order, successfully rotating the list to the right by 2 positions.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list.

The algorithm performs the following operations:

1. First traversal to count the total number of nodes: O(n)
2. Calculate k % n: O(1)
3. Move the fast pointer k steps ahead: O(k), where k < n after the modulo operation
4. Move both fast and slow pointers until fast reaches the last node: O(n - k)

Total time: O(n) + O(1) + O(k) + O(n - k) = O(n)

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• A few pointer variables (cur, fast, slow, ans)
• An integer variable n to store the count
• No additional data structures are created

All operations are performed in-place by manipulating the pointers of the existing linked list nodes, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling k Greater Than List Length

One of the most common mistakes is forgetting to handle cases where k is greater than the length of the linked list. Without the modulo operation, the fast pointer would try to move beyond the list boundaries, causing a null pointer exception.

Incorrect approach:

# This will crash if k > list_length
fast = head
for _ in range(k):  # If k > n, fast will become None
    fast = fast.next  # NullPointerException when fast is None

Solution: Always calculate k % list_length before using k to move pointers. This ensures k is within valid bounds and avoids unnecessary full rotations.

Pitfall 2: Off-by-One Error in Pointer Movement

A frequent error occurs when developers move the fast pointer to the wrong position, often moving it k+1 or k-1 steps instead of exactly k steps, resulting in incorrect rotation.

Incorrect approach:

# Moving fast pointer to wrong position
while fast.next and k > 0:  # This might not move exactly k steps
    fast = fast.next
    k -= 1

Solution: Use a precise loop to move the fast pointer exactly k steps:

for _ in range(k):
    fast = fast.next

Pitfall 3: Forgetting to Break the Original Link

When performing the rotation, forgetting to set slow.next = None creates a cycle in the linked list instead of properly rotating it.

Incorrect approach:

new_head = slow.next
# Forgot: slow.next = None
fast.next = head  # This creates a cycle!
return new_head

Solution: Always remember to break the link at the rotation point before reconnecting:

new_head = slow.next
slow.next = None  # Critical: break the link to avoid cycle
fast.next = head

Pitfall 4: Not Checking for k = 0 After Modulo

After calculating k % list_length, if k becomes 0, the list doesn't need rotation. Continuing with the algorithm unnecessarily complicates the logic and may lead to errors.

Incorrect approach:

k = k % list_length
# Not checking if k == 0, continuing with unnecessary operations
fast = slow = head
# ... rest of the code

Solution: Always check if k equals 0 after the modulo operation and return early:

k = k % list_length
if k == 0:
    return head

Pitfall 5: Incorrect Traversal to Count List Length

Using the wrong variable or condition when counting nodes can lead to an incorrect count, affecting the modulo calculation.

Incorrect approach:

n = 1  # Starting with 1 instead of 0
cur = head
while cur.next:  # This misses counting the last node
    n += 1
    cur = cur.next

Solution: Start counting from 0 and traverse until the current node is None:

n = 0
cur = head
while cur:
    n += 1
    cur = cur.next