Problem Statement

Given a singly linked list, rotate the list to the right by k places, where k is a non-negative integer.

Examples

Example 1:

Input: 1 -> 2 -> 3 -> 4 -> 5, k = 2
Output: 4 -> 5 -> 1 -> 2 -> 3

Explanation: Rotate the list to the right by 2 places. The last two nodes (4, 5) are moved to the front.
List after 1 shift to right: 5->1->2->3->4
List after 2 shift to right: 4->5->1->2->3

Example 2:

Input: 0 -> 1 -> 2, k = 4
Output: 2 -> 0 -> 1

Explanation: Rotate the list to the right by 4 places. Since k is greater than the length of the list, it effectively rotates by k % length (4 % 3 = 1).

Example 3:

Input: 1, k = 3
Output: 1

Explanation: The list has only one node, so rotating it by any number of places results in the same list.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

For each k step, move the last element of a linked list to the front. This shifts all elements from one position to the right, with the last element wrapping around to become the first.

Approach:

1. Move the last element to first for each k.
2. For each k, find the last element from the list. Move it to the first.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode() {
        val = 0;
        next = NULL;
    }
    ListNode(int data1) {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1) {
        val = data1;
        next = next1;
    }
};

class Solution {
public:
    // Function to rotate the list by k steps
    ListNode* rotateRight(ListNode* head, int k) {
        // Base case: if list is empty or has only one node
        if (head == NULL || head->next == NULL) return head;

        // Perform rotation k times
        for (int i = 0; i < k; i++) {
            ListNode* temp = head;
            // Find the second last node
            while (temp->next->next != NULL) 
                temp = temp->next;
            // Get the last node
            ListNode* end = temp->next;
            // Break the link between 
            // second last and last node
            temp->next = NULL;
            // Make the last node 
            // as new head
            end->next = head;
            head = end;
        }
        return head;
    }
};

// Utility function to insert node at the end of the list
void insertNode(ListNode* &head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == NULL) {
        head = newNode;
        return;
    }
    ListNode* temp = head;
    while (temp->next != NULL) temp = temp->next;
    temp->next = newNode;
}

// Utility function to print list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val;
        if (head->next != NULL) cout << "->";
        head = head->next;
    }
    cout << endl;
}

int main() {
    ListNode* head = NULL;
    // Inserting nodes
    insertNode(head, 1);
    insertNode(head, 2);
    insertNode(head, 3);
    insertNode(head, 4);
    insertNode(head, 5);

    cout << "Original list: ";
    printList(head);

    int k = 2;
    Solution solution;
    // Calling function for rotating right by k times
    ListNode* newHead = solution.rotateRight(head, k);

    cout << "After " << k << " iterations: ";
    // List after rotating nodes
    printList(newHead);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(NxK) because for K times, we are iterating through the entire list to get the last element and move it to the first position. Here, N represents the number of nodes in the linked list, and K is the number of steps by which the list has to be rotated.
• Space Complexity: O(1) because no extra data structure is required for computation.

2️⃣ Optimal Approach

Intuition

To rotate a linked list to the right by k places, you can think of it as moving the last k nodes to the front. Here’s a step-by-step approach to solve the problem:

1. Determine the Length of the List:
   Calculate the length of the linked list. This helps in finding the actual number of rotations needed when k is larger than the length.
2. Calculate Effective Rotations:
   If k is greater than the length of the list (n), rotating n times or n + n times results in the same list. So, the effective number of rotations needed is k % n.
3. Find the New End and New Head:
   To perform the rotation:
   • Find the new end of the list, which is the (n - k)-th node from the beginning.
   • The node right after this node will be the new head of the rotated list.
4. Rotate the List:
   Break the link between the new end and the new head, and connect the original last node to the original head to complete the rotation.

Code:

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* rotateRight(ListNode* head, int k) {
    if (!head || k == 0) return head;

    // Calculate the length of the linked list
    int length = 1;
    ListNode* tail = head;
    while (tail->next) {
        tail = tail->next;
        length++;
    }

    // Calculate the effective rotations needed
    k = k % length;
    if (k == 0) return head; // No rotation needed

    // Find the new end of the list
    ListNode* new_end = head;
    for (int i = 1; i < length - k; i++) {
        new_end = new_end->next;
    }

    // The node after new_end will be the new head
    ListNode* new_head = new_end->next;

    // Rotate the list
    new_end->next = nullptr;
    tail->next = head;

    return new_head;
}

// Utility function to print the linked list
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

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

    std::cout << "Original list: ";
    printList(head); // Output: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr

    int k = 2;
    head = rotateRight(head, k);

    std::cout << "Rotated list by " << k << ": ";
    printList(head); // Output: 4 -> 5 -> 1 -> 2 -> 3 -> nullptr

    return 0;
}

Complexity Analysis

1. Time Complexity:
   • O(N): The function traverses the linked list twice, once to calculate its length and again to find the new end and rotate the list.
2. Space Complexity:
   • O(1): The function uses a constant amount of extra space for pointers.

Same Idea Another Implementation:

Intuition

For every k that is a multiple of the length of the list, the linked list returns to its original state after rotation. By using brute force with k as a multiple of the list's length, we notice this pattern. This insight suggests that for k greater than the length of the list, we only need to rotate the list by k % length of the list, thus optimizing our time complexity.

Approach:

1. Calculate the length of the list.
2. Connect the last node to the first node, converting it to a circular linked list.
3. Iterate to cut the link of the last node and start a node of k%length of the list rotated list.

Code:

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || head->next == nullptr || k == 0) {
            return head; // Handle edge cases
        }

        // Step 1: Find the length of the list
        int length = 1; // Initialize to 1 to account for the head node
        ListNode* temp = head;
        while (temp->next != nullptr) {
            length++;
            temp = temp->next;
        }

        // Step 2: Update k to avoid unnecessary rotations
        k = k % length;
        if (k == 0) {
            return head; // No rotation needed
        }

        // Step 3: Connect the tail to the head to form a circular list
        temp->next = head;

        // Step 4: Find the new tail (length - k - 1 steps from the head)
        int stepsToNewTail = length - k;
        ListNode* newTail = head;
        for (int i = 1; i < stepsToNewTail; i++) {
            newTail = newTail->next;
        }

        // Step 5: Set the new head and break the circular connection
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;

        return newHead;
    }
};

Complexity Analysis:

• Time Complexity: O(n)
  • One pass to find the length and another to adjust pointers.
• Space Complexity: O(1)
  • No additional space is used.