Rotate List medium

Problem Statement

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]

Steps

1. Find the list length: Traverse the linked list to determine its length n.
2. Handle edge cases: If the list is empty (n == 0) or k is a multiple of n, no rotation is needed. Return the original head.
3. Adjust k: If k is larger than n, reduce k modulo n to handle rotations larger than the list length.
4. Find the new tail: Traverse the list to the node that will become the new tail ( n - k -1 nodes from the head).
5. Update pointers:
   • Set the next pointer of the new tail to nullptr (making it the new tail).
   • Set the next pointer of the original tail to the original head.
   • Update the head pointer to the node after the new tail.

Explanation

The core idea is to treat the linked list as a circular structure. We find the point where the list should be broken to create the rotated list. Then we carefully adjust pointers to connect the two parts. The modulo operation (k % n) ensures that we handle rotations larger than the list's length efficiently.

Code

#include <iostream>

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) {}
};

ListNode* rotateRight(ListNode* head, int k) {
    if (head == nullptr || head->next == nullptr) return head; //Handle empty or single-node lists

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

    k = k % n; //Handle k > n
    if (k == 0) return head; //No rotation needed

    int newTailIndex = n - k - 1;
    ListNode* newTail = head;
    for (int i = 0; i < newTailIndex; ++i) {
        newTail = newTail->next;
    }

    ListNode* newHead = newTail->next;
    tail->next = head;
    newTail->next = nullptr;

    return newHead;
}


int main() {
    // Example usage:
    ListNode* 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);

    int k = 2;
    ListNode* rotatedHead = rotateRight(head, k);

    while (rotatedHead != nullptr) {
        std::cout << rotatedHead->val << " ";
        rotatedHead = rotatedHead->next;
    }
    std::cout << std::endl; // Output: 4 5 1 2 3

    return 0;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We traverse the list multiple times, but each traversal is linear in the list's size.
• Space Complexity: O(1). We use only a constant amount of extra space to store pointers.