Rotate List

How it works

We can simplify the two-pointer approach by first creating a circular list. Connect the tail to the head, then traverse n - k steps from the tail to find the new tail. Break the circle at that point. This approach uses a single pointer and avoids the need to track both the tail and find the break point separately.

Steps

1. If the list is empty, return null.
2. Traverse to find the tail and count the length n.
3. Connect the tail to the head, forming a circular list.
4. Compute k = k % n to handle large values of k.
5. Move n - k steps from the current position (the tail) to reach the new tail.
6. The new head is the node after the new tail.
7. Break the circle by setting the new tail's next to null.
8. Return the new head.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Not Handling Empty List or Single Node

Forgetting to check if the list is empty (head == null) or has only one node causes null pointer exceptions. A single-node list rotated by any amount remains unchanged, but the code must handle this edge case explicitly.

Forgetting to Normalize k by List Length

When k is larger than the list length or equals it, the rotation results in the same list. Failing to compute k = k % length before rotation leads to unnecessary traversals or incorrect results. Additionally, when k % length == 0, no rotation is needed and the original head should be returned.

Incorrectly Breaking and Reconnecting the List

When creating the new list structure, forgetting to set the new tail's next to null creates a cycle in the linked list. Similarly, forgetting to connect the old tail to the old head leaves the list disconnected. Both pointer updates are essential for correct rotation.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return head

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

        cur.next = head
        k %= n
        for i in range(n - k):
            cur = cur.next

        head = cur.next
        cur.next = None
        return head

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) {
            return head;
        }

        ListNode* cur = head;
        int n = 1;
        while (cur->next) {
            n++;
            cur = cur->next;
        }

        cur->next = head;
        k %= n;
        for (int i = 0; i < n - k; i++) {
            cur = cur->next;
        }

        head = cur->next;
        cur->next = nullptr;
        return head;
    }
};