Rotate a Linked List

Given the head of a singly linked list, your task is to left rotate the linked list k times.

Examples:

Input: head = 10 -> 20 -> 30 -> 40 -> 50, k = 4
Output: 50 -> 10 -> 20 -> 30 -> 40
Explanation:
Rotate 1: 20 -> 30 -> 40 -> 50 -> 10
Rotate 2: 30 -> 40 -> 50 -> 10 -> 20
Rotate 3: 40 -> 50 -> 10 -> 20 -> 30
Rotate 4: 50 -> 10 -> 20 -> 30 -> 40

Input: head = 10 -> 20 -> 30 -> 40 , k = 6
Output: 30 -> 40 -> 10 -> 20 
 

Constraints:

• 1 <= number of nodes <= 10⁵
• 0 <= k <= 10⁹
• 0 <= data of node <= 10⁹

Approach 01:

class Solution {
  public:
    Node* rotate(Node* head, int k) {
        // Calculate the length of the linked list
        int listLength = 1;
        Node* lastNode = head; // Pointer to the last node
        while (lastNode->next != NULL) {
            lastNode = lastNode->next;
            listLength++;
        }

        // Make the linked list circular
        lastNode->next = head;

        // Calculate the effective rotation count
        k = k % listLength;

        // Find the new head after rotation
        Node* newHead = head;
        while (k > 0) {
            newHead = newHead->next;
            k--;
        }

        // Break the circular linked list to finalize rotation
        Node* temp = newHead;
        while (listLength > 1) {
            temp = temp->next;
            listLength--;
        }
        temp->next = NULL;

        return newHead;
    }
};

class Solution:
    def rotate(self, head, k):
        # Calculate the length of the linked list
        listLength = 1
        lastNode = head  # Pointer to the last node
        while lastNode.next:
            lastNode = lastNode.next
            listLength += 1

        # Make the linked list circular
        lastNode.next = head

        # Calculate the effective rotation count
        k = k % listLength

        # Find the new head after rotation
        newHead = head
        while k > 0:
            newHead = newHead.next
            k -= 1

        # Break the circular linked list to finalize rotation
        temp = newHead
        while listLength > 1:
            temp = temp.next
            listLength -= 1
        temp.next = None

        return newHead

Time Complexity:

• Length Calculation:

  To calculate the length of the linked list, we traverse it once, which takes \( O(n) \), where \( n \) is the number of nodes in the list.

• Rotation Count Calculation:

  The modulo operation \( k = k \% \text{listLength} \) takes \( O(1) \).

• Finding New Head:

  To find the new head after rotation, we traverse \( k \) nodes, which takes \( O(k) \).

• Breaking the Circular Link:

  To traverse the remaining nodes to break the circular linked list, we take \( O(n – k) \).

• Overall Time Complexity:

  The total time complexity is \( O(n) \), as \( O(k) + O(n – k) = O(n) \).

Space Complexity:

• Auxiliary Space:

  No extra space is used apart from a few pointers. Therefore, the auxiliary space complexity is \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).