 # 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){
}
``````

//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){
}
``````

//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``````