61. Rotate List

Problem Description

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:

• The number of nodes in the list is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9

Solution: Fast and Slow Pointers + Linked List Concatenation

This solution uses a two-pointer approach for efficiency. Here's a breakdown:

1. Handle trivial cases: If the list is empty or has only one node, no rotation is needed, so we return the head.

2. Find list length: We traverse the list once to determine the total number of nodes (n).

3. Adjust k: Since k can be larger than the list length, we use the modulo operator (k %= n) to find the effective number of rotations. If k is 0 after this, no rotation is necessary.

4. Find split point: We use two pointers, fast and slow, both initially at the head. We advance fast by k steps. Then, we move both fast and slow simultaneously until fast reaches the end of the list. At this point, slow points to the node just before the new head.

5. Rotate: We break the list at slow, making slow.next the new head. We then connect the tail (fast) to the original head.

6. Return new head: The new head (ans) is returned.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list a constant number of times (at most three).
• Space Complexity: O(1). We use only a constant amount of extra space for pointers.

Code Implementation

The code is provided in multiple languages in the original prompt. The core logic remains consistent across all implementations. They follow the steps outlined above. Each language's specific syntax is used to manipulate the linked list nodes. For example, pointer manipulation in C++ differs from that in Python. However, the algorithm's fundamental steps are identical.