C++ O(n) Simple Four step solution with explanation


#1

Simple four step process

  1. Rotate Entire List

  2. Traverse to kth position in reversed list and break it into two parts

  3. Reverse the two parts individually

  4. Merge the reverse first part to reversed second part

     if(!head || !head->next || k==0){
         return head;
     }
    

    //Find length of entire list and Reduce list size by taking mod

    int len=length(head); k%=len;

    //if size of list is equal to k or multiple of k simply return head

     if(k==0){
         return head;
     }
    

//Reverse the entire list

ListNode*rev=reverse(head);  
ListNode*first=rev;

//Iterate to position k

int count=1;   
while(rev && count!=k){
    rev=rev->next;
    count++;
}

//Split the list into two parts

ListNode*second=rev->next;  
rev->next=NULL;

//Reverse the two parts formed (first and second)

first=reverse(first);
second=reverse(second);

//Now merge the first part to second

ListNode*itr=first;   
while(itr && itr->next){
    itr=itr->next;
}
itr->next=second;
return first; //Return first