#61 Rotate List - Solution

The Rotate List problem asks you to rotate a singly linked list to the right by k positions. A straightforward idea is to repeatedly move the last node to the front, but this becomes inefficient for large k. A more optimal strategy relies on understanding the length of the list and using a two-pointer technique.

First, traverse the list to compute its length and identify the tail node. Since rotating by the list length results in the same list, reduce the rotations using k % length. Then locate the new tail by moving length - k - 1 steps from the head. The node after this becomes the new head. By temporarily connecting the tail to the head, you can treat the list as circular and then break the link at the correct position.

This approach efficiently performs the rotation in O(n) time with O(1) extra space.

Approach	Time Complexity	Space Complexity
Length Calculation + Two Pointer Rotation	O(n)	O(1)

Solutions (7)

Approach 1: Convert to Circular List

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.

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.

C Java Python JavaScript

1class ListNode:
2    def __init__(self, x):
3        self.val = x
4        self.next = None
5
6class Solution:
7    def rotateRight(self, head: ListNode, k: int) -> ListNode:
8        if not head or k == 0:
9            return head
10        # Compute the length of the list
11        length = 1
12        current = head
13        while current.next:
14            current = current.next
15            length += 1
16        current.next = head  # make circular
17        k = k % length
18        # Calculate the position to break at
19        for _ in range(length - k):
20            current = current.next
21        new_head = current.next
22        current.next = None
23        return new_head
24
25# Example usage
26head = ListNode(1)
27head.next = ListNode(2)
28head.next.next = ListNode(3)
29head.next.next.next = ListNode(4)
30head.next.next.next.next = ListNode(5)
31solution = Solution()
32rotated_head = solution.rotateRight(head, 2)
33current = rotated_head
34while current:
35    print(current.val, end=' ')
36    current = current.next
37

Explanation

The Python solution implements the same algorithm. Traverse the list to make it circular by connecting the last node's next pointer to the head. Use the length of the list to handle cases where k is larger than the list length. Break the circle to form the rotated list.

This code also contains a usage example to demonstrate its working.

Approach 2: Two-Pointer Technique

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.

Time Complexity: O(n) because it requires traversal for counting.
Space Complexity: O(1) as no extra space is used.

C++Python C#

1#include <iostream>
2using namespace std;
3
4struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || k == 0) return head;
        ListNode* fast = head, *slow = head;
        int length = 1;
        while (fast->next) {
            fast = fast->next;
            ++length;
        }
        fast->next = head;
        k %= length;
        for (int i = 0; i < length - k; i++) {
            slow = slow->next;
            fast = fast->next;
        }
        head = slow->next;
        fast->next = NULL;
        return head;
    }
};

// Example usage
int main() {
    auto *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    Solution sol;
    head = sol.rotateRight(head, 2);
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}