61. Rotate List

📝 Problem Details

• Title: 61. Rotate List
• Link: https://leetcode.com/problems/rotate-list/
• Difficulty: Medium
• Tags/Categories: Linked-List Math

💭What Were My Initial Thoughts?

- interate through the list with an iterator node
- cumulate the length of the list

- use the list and k value to compute k%n which is the condensed number of k rotations

🤔What Did I Struggle With?

- took me a while to solidify the above approach
- ran out of time 
- probably would've had issues with cutting the tail of the previous tail node that will be moved to the head

💡 Explanation of Solution

- count the number of nodes in the list
- find the tail of the list, create a circular linked list by connecting the tail to the head
- conduct rotations 
- cut off tail 

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr) return head;
 
        int n = 1; //number of nodes in the list
 
        ListNode* tail = head;
        ListNode* newHead = tail;
 
        while(tail->next) { // get the number of nodes in the list
            tail = tail->next;
            n++;
        }
        tail->next = head;  // circle the link
 
        if(k %= n) {
            for(auto i=0; i < n-k; i++) {
                tail = tail->next;
            }
        }
 
        newHead = tail->next;
        tail->next = nullptr;
        return newHead;
 
    }
};