61. Rotate List - Detailed Explanation

Problem Statement

Given the head of a linked list, rotate the list to the right by k places. In other words, move the last k nodes to the beginning of the list in order. If k is greater than the length of the list, it wraps around using modulo arithmetic.

For example, if you have the list:
1 → 2 → 3 → 4 → 5
and k = 2, after rotating the list the result is:
4 → 5 → 1 → 2 → 3

Example Inputs, Outputs, and Explanations

Example 1

• Input: head = [1, 2, 3, 4, 5], k = 2
• Output: [4, 5, 1, 2, 3]
• Explanation:
  The last two nodes (4 and 5) are moved to the front of the list.

Example 2

• Input: head = [0, 1, 2], k = 4
• Output: [2, 0, 1]
• Explanation:
  Since k = 4 is greater than the list length (3), we use k % 3 = 1. Rotating by 1 position moves the last node (2) to the front.

Hints

1. Compute the Length:
   Traverse the list to determine its length. This also gives you access to the tail of the list.

2. Effective Rotation:
   Since rotating by the length of the list results in the same list, compute the effective rotations using k % length.

3. Make the List Circular:
   Connect the tail of the list to the head to create a circular list. Then, break the circle at the appropriate position to form the rotated list.

4. Determine the New Head:
   The new head is located at position (length - (k % length)) from the beginning. The node right before the new head becomes the new tail.

Approach: Using a Circular List

Explanation

1. Edge Cases:
   If the list is empty, contains a single node, or k is 0, return the head immediately.

2. Calculate Length and Tail:
   Traverse the list to calculate its length and identify the tail node.

3. Effective Rotations:
   Calculate the effective rotations with k = k % length. If the effective k is 0, no rotation is needed.

4. Create a Circular List:
   Connect the tail's next pointer to the head, forming a circular linked list.

5. Find the New Tail and New Head:
   The new tail is the node at position (length - k - 1) from the start, and the new head is newTail.next.

6. Break the Circle:
   Set newTail.next to null to break the circular link, resulting in the rotated list.

Step-by-Step Walkthrough

Consider the list: 1 → 2 → 3 → 4 → 5 with k = 2

1. Calculate length: length = 5, tail = node with value 5.

2. Effective rotation: k = 2 % 5 = 2.

3. Form a circle: tail.next = head (5 → 1).

4. New tail position: index = length - k - 1 = 5 - 2 - 1 = 2 (0-indexed, node with value 3).

5. New head: newTail.next (node with value 4).

6. Break the circle: set newTail.next = null.
   Resulting list: 4 → 5 → 1 → 2 → 3

Python Code

Complexity Analysis

• Time Complexity: O(n)
  Traversing the list to compute the length, forming the circular link, and then finding the new tail all require linear time relative to the number of nodes.

• Space Complexity: O(1)
  Only a few pointers and variables are used, regardless of the list size.

Common Mistakes and Edge Cases

• Not Handling k Greater Than Length:
  Always compute k modulo the length of the list; failing to do so might lead to unnecessary rotations.

• Edge Cases:
  If the list is empty or contains only one node, no rotation is needed.

• Breaking the Circular Link:
  After forming the circular list, ensure that the circle is properly broken by setting newTail.next to null to prevent infinite loops.

Alternative Variations

• Left Rotation:
  A similar approach can be used to rotate the list to the left by k positions. The key differences involve calculating the new head position differently.

Related Problems

• Reverse Linked List:
  A fundamental problem for understanding linked list manipulation.

• Merge Two Sorted Lists:
  Another common linked list problem that helps build the foundation for list manipulations.