[WIP] 61. Rotate List

Question

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]

Constraints:

• The number of nodes in the list is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

---

Approach

Solution

/**
 * 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) {
        int len = 1;
        ListNode* curr = head;
        ListNode* temp = head;

        if(head == NULL) return head;
        
        //find len of list
        while(curr->next != NULL){
            len++;
            curr= curr->next;
        }
                
        //modulo to prevent uneccesary rotation
        k = k % len;
        
        //rotate k times
        while(k--){
            //make circular LL
            while(temp->next != NULL){
                temp = temp->next;
            }
            temp->next = head;
            
            //last node as new head
            head = temp;
            curr = temp;
            
            //move to node before last node
            while(temp->next != head){
                temp= temp->next;
            }
            
            //make tail empty
            temp->next = NULL;
            
            temp = curr;
        }
        return head;
    }
};