# 61 Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

題目是要位移linked list，但仔細發現每次都是移動2個Node，且除k%size==0之外，每次最後一個Node的next都會指向第一個Node。因為k值是從最後一個Node數過來，所以個人做法是先取到head linked list的長度size，然後再用size - k 取得 head應該指向的Node。舉例:

Input:  1->2->3->4->5->NULL, k = 2
從後面數過來第k個(2)  即是 4 Node ，這個Node就是 head要指向的位置
但從前面數來是x ，x = size-k， 這裡要注意是k可能會大於size，所以
x = size-k  轉成==> x = size-(k%size) 無論k多大，取k/size的餘數一定不會大於size。
此範例x = 3，從前面數來第三個Node 即 3 Node，3 Node的next 指向null。
Node.next = null;這樣head就指不到 4 Node了，所以head先指向4 Node後，3 Node的next(原指向4 Node)
改指向null;

Output: 4->5->1->2->3->NULL

也發現每次位移都是 目標Node指向null，目標Node的next為head
Input:  1->2->3->4->5->NULL, k = 2  目標Node 3指向null ，Node 3的next 為head 且最後一個Node指向第一個Node
Output: 4->5->1->2->3->NULL

Input:  1->2->3->4->5->NULL, k = 3  目標Node 2指向null ，Node 2的next 為head 且最後一個Node指向第一個Node
Output: 3->4->5->1->2->NULL

程式碼:

/**
 * 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){
            return head;
        }
        
        // Node is not public in java.util.stream; cannot be accessed from outside package
        ListNode tail = head;
        int size = 1;
        int target = 0;
        while(tail.next != null){
            size++;
            tail = tail.next;
        }
        if(k%size == 0){
            return head;
        }
        target = size- (k% size);
        //目標的下一個是F, 目標的next指向null
        // System.out.println("size = "+ size + " , tail.val = " + tail.val + " ,target = " + target + " , k = " + k + " , k%size = " + (k%size) );
        
        tail.next = head;
        tail = head;
        int ii = 1;
        while(tail != null){
            if(ii == target){
                head = tail.next;
                tail.next = null;
            }
            tail = tail.next;
            ii++;
        }
        
        // //print
        // ListNode t = f;
        // while(t != null){
        //     System.out.println("t.val = " + t.val);
        //     t = t.next;
        // }
        // //piint
        return head;
    }
}