61. Rotate List

Difficulty: Medium

Topics: Linked List, Two Pointers

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]

Example 3:

Input: head = [1], k = 0
Output: [1]

Example 4:

Input: head = [1,2,3], k = 0
Output: [1,2,3]

Example 5:

Input: head = [], k = 5
Output: []

Example 6:

Input: head = [1,2,3], k = 5
Output: [2,3,1]

Constraints:

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

Solution:

This solution rotates a singly linked list to the right by k places in O(n) time and O(1) space. It first computes the list length, reduces k modulo the length, finds the new head and tail, then performs the rotation by linking the tail to the old head and breaking the list at the new tail.

Approach:

Find list length and tail node to handle cases where k is larger than the list length.
Reduce k by taking k % length to avoid unnecessary rotations.
Locate new tail at position length - k - 1 using traversal from head.
Perform rotation by making the original tail point to the original head, and the new tail point to null.
Return new head, which is the node after the new tail.

Let's implement this solution in PHP: 61. Rotate List

<?php
/**
 * @param ListNode $head
 * @param Integer $k
 * @return ListNode
 */
function rotateRight($head, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo rotateRight([1,2,3,4,5], 2) . "\n";        // Output: [4,5,1,2,3]
echo rotateRight([0,1,2], 4) . "\n";            // Output: [2,0,1]
echo rotateRight([1], 0) . "\n";                // Output: [1]
echo rotateRight([1,2,3], 0) . "\n";            // Output: [1,2,3]
echo rotateRight([], 5) . "\n";                 // Output: []
echo rotateRight([1,2,3], 5) . "\n";            // Output: [2,3,1]
?>

Explanation:

Edge Cases If the list is empty, has one node, or k == 0, return the head immediately.
Find length and tail Traverse the list to count nodes and store the last node.
Optimize k Since rotating by length gives the same list, set k = k % length. If k == 0, no rotation is needed.
Find new tail position The new tail is at index length - k - 1 (0-based). Traverse from head to this node.
Re-link nodes
- Original tail's next points to original head (close loop).
- New tail's next is set to null (break loop).
- New head is newTail->next.
Return new head This completes the rotation.

Complexity

Time Complexity: O(n) - One pass to find length, another partial pass to find new tail.
Space Complexity: O(1) - Only a few pointers used, no extra data structures.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub