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

/**
 * 61. Rotate List
 * https://leetcode.com/problems/rotate-list/
 * https://real-neo.me/61-rotate-list/
 */
class RotateList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 10; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        RotateList solution = new RotateList();

        solution.print(head);
        System.out.println("Rotate 1");
        head = solution.rotateRight(head, 1);
        solution.print(head);
        System.out.println("Rotate 1");
        head = solution.rotateRight(head, 1);
        solution.print(head);
        System.out.println("Rotate 3");
        head = solution.rotateRight(head, 3);
        solution.print(head);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    private ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null)
            return head;
        ListNode node = head;
        int length = 1;
        while (node.next != null) {
            node = node.next;
            length++;
        }
        k = k % length;
        k = length - k; //值的范围 [1, length],表示要进行移动的次数
        //循环链表
        node.next = head;
        while (k > 0) {
            head = head.next;
            node = node.next;
            k--;
        }
        node.next = null;
        return head;
    }
}