Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
Solution：Two Pointers
思路：因为k可以是 > linklist.length的，所以需要知道linklist的长度length找到k = k % length实际rotate的位置。既然求出了length，就不用gap+first/second指针找到
Time Complexity: O(N) Space Complexity: O(N)
Solution Code：
class Solution {
public ListNode rotateRight(ListNode head, int k) {
// 1 -> 2 -> 3 -> 4 -> 5 -> null, k = 2
// cur tail
if(head == null) return null;
// get length of the list
int length = 1;
ListNode tail = head;
while(tail.next != null) {
tail = tail.next;
length++;
}
// get effective k
k = k % length;
if(k == 0) return head;
// find pos to rotate
ListNode cur = head;
for(int i = 0; i < length - k - 1; i++) {
cur = cur.next;
}
// relink
tail.next = head;
ListNode new_head = cur.next;
cur.next = null;
return new_head;
}
}
