#### Approach #1 Two Pointers [Time Limit Exceeded]

**Intuition**

Find the $$k$$'th position from the end, cut the list form there then move second part in front of first part.

**Algorithm**

List is Single Linked List and we need to cut it at k'th position from tail. As there is only forward links, we need to figure out a way to find it form beginin of linked list.

One quick approach will be iteration form the head to tail and cmoputing the list $$length$$. then the cut point will be $$length-k$$'th position. Then in a second tour the list will be cut at that point and and the second half will be moved to in front of the List.

```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || k ==0 )
return head;
ListNode first;
ListNode second;
first=head;
int i=0;
while(i++ < k ){
first = first.next;
if(first == null){ // that means k > l. choose to return
first = head;
}
}
second =head;
while(first.next!=null){
first=first.next;
second=second.next;
}
//now second points to element at l-k
first.next = head;
ListNode nth=second.next;
second.next = null;
return nth;
}
}
```

**Complexity Analysis**

- Time complexity : $$O(k)$$.

To find k'th position, algorithm traverses k times. rest of the operations are constant time.

#### Approach #2 Avoiding multiple traversals [Accepted]

**Algorithm**

Previous approach have $$O(k)$$ time complexity. When this $$k$$ is too large, the solution will fail to finish in expected time limits.

In order to find $$k$$'th position, multiple times the list might traversed. However, those extra traversal can be avoided by checking the list $$length$$ and $$k$$ values. A large k'th value equal to length would have no effect on the list.

Rotation the list by its length is equal to initial list. So, for large k values, only $$k~mod~length$$ many rotation is needed.

**Java**

```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || k ==0 )
return head;
ListNode first;
ListNode second;
first=head;
int i=0;
while(i++ < k ){
first = first.next;
if(first == null){ // that means k > l. choose to return
first = head;
int length = i;
i=0;
k=k%length;
}
}
second =head;
while(first.next!=null){
first=first.next;
second=second.next;
}
//now second points to element at l-k
first.next = head;
ListNode nth=second.next;
second.next = null;
return nth;
}
}
```

**Complexity Analysis**

Algorithm traverse up to end of list which take $$n$$ operations then take $$k~mod~length$$ more steps which is smaller then $$n$$.

So, time complexity is $$O(2n) = O(n)$$.