61. Rotate List

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;
    }
}