DAY 101 - 61. Rotate List

Hey Everyone!, a bit change of plans, I will be continuing this series until I accidentally break it.

Today we are going to do another linked list question, which is quite encountered in arrays as well is rotate the linked list.

Question: Rotate List

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]

Understanding the Problem

Before we dive into the code, let's break down the problem and understand its requirements:

• We're given a linked list head where each node contains a value.

• We need to perform operations in the such that list should be rotated to the right by k positions.

• We need to return the head of the new linked list after the rotation.

Intuition:

• We've encountered such type of problems in arrays first and truth be told, we are not going to change our approach much here.
• We know that if k > length of the list we need it's modulus because it's just one length wrapped around + rotations. -We need to find out what will be the end in our rotated list.
• Our len - k will give us the ending node of the final list, so now we know what should be null.
• We just make the node next to it head and our ending point null after making it a circular list.
• Let's write approach for better understanding.

The Approach

1. Base Cases: First, we handle the base cases where no rotation is needed or where the input linked list is empty or contains only one node. In these cases, we directly return the head since no rotation is required.

2. Calculate the Length: We need to determine the length of the linked list to understand how many positions to rotate. We traverse the linked list once and count the number of nodes to find the length.

3. Make the List Circular: Since the rotation should wrap around, we connect the last node to the head, effectively making it circular.

4. Calculate the New Head: To find the new head of the rotated list, we need to locate the node that will become the first node in the rotated list. This node is located at a position len - k, where len is the length of the list and k is the number of positions to rotate.

5. Break the Circular List: After determining the new head, we need to break the circular list. We set the next of the node at position len - k to nullptr.

6. Return the Result: Finally, we return the new head, which represents the rotated linked list.

Code:

/**
 * 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 == nullptr || head->next == nullptr || k == 0){
            return head;
        }

        //only rotate by len % k
        int len = 1;
        ListNode* temp = head;
        while(temp->next){
            temp = temp->next;
            len++;
        }

        //we got the length now;
        //make it circular
        temp->next = head;
        k = k % len;
        int end = len - k;

        while(end--){
            temp = temp->next;

        }

        head = temp->next;
        temp->next = nullptr;


        return head;

    }
};

Complexity Analysis:

• Time Complexity: The algorithm makes a single pass through the linked list to calculate its length, so its time complexity is O(N), where N is the number of nodes in the linked list.

• Space Complexity: The algorithm uses a constant amount of extra space for variables, so the space complexity is O(1).