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.

** 解题思路 **
用快慢指针，分三步来做。第一步用fast 指针算出链表长度；第二步用slow 指针定位要旋转的位置；第三步作旋转。
Since n may be a large number compared to the length of list. So we need to know the length of linked list.After that, move the list after the (l-k%l )th node to the front to finish the rotation.

Ex: {1,2,3} k=2 Move the list after the 1st node to the front

Ex: {1,2,3} k=5, In this case Move the list after (3-5%3=1)st node to the front.

So the code has three parts.

(1) Get the length

(2) Move to the (l-k%l)th node

(3)Do the rotation

 public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        int size = 0;
        // Get the total length
        while (fast.next != null) {
            size++;
            fast = fast.next;
        }
        // Get the size - k % size th node
        for (int j = size - k % size; j > 0; j--) {
           slow = slow.next;   
        }
        // do the rotation
        fast.next = dummy.next;
        dummy.next = slow.next;
        slow.next = null;
        
        return dummy.next;
    }