class Solution {
    public static ListNode nail;//尾指针

    public ListNode rotateRight(ListNode head, int k) {
        int l = 0;//链表长度
		nail=null;
        for (ListNode i = head; i != null; i = i.next) {
            l++;
            if (i.next == null) {
                nail = i;
            }
        }
        if (k == 0 || l == 1||l==0)
        return head;

        k = k % l;

        for (int i = 0; i < k; i++) {

            int v=nail.val;
            //注意: java只有值传递 ,所以修改后的head要返回接收
            head=head_insert(v,head);  
            delete_nail(head);
        }
        return head;
    }

    //head前面插入一个节点
    public ListNode head_insert(int v, ListNode head) {
        ListNode ln = new ListNode(v);
        ln.next = head;
        return ln;
    }

    //尾部删除一个节点
    public void delete_nail(ListNode head) {

        //遍历找到倒数第二个节点
        ListNode s = head;
        while (s.next != nail) {
            s = s.next;
        }
        s.next = null;//删除
        //更新尾节点
        nail = s;
    }

}

/*
原始: 1 -> 2 -> 3 -> 4 -> 5, k=2

步骤1: 找到尾节点
1 -> 2 -> 3 -> 4 -> 5
               ↑tail

步骤2: 计算 n=5, k=2, n-k=3

步骤3: 找到新尾节点（第3个节点）
1 -> 2 -> 3 -> 4 -> 5
          ↑newTail

步骤4: 重组链表
newTail.next = null
tail.next = head

结果: 4 -> 5 -> 1 -> 2 -> 3
*/

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        // 1. 计算长度，并找到尾节点
        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }
        
        // 2. 优化旋转次数
        k = k % n;
        if (k == 0) return head;
        
        // 3. 找到新的尾节点（正数第 n-k 个节点）
        ListNode newTail = head;
        for (int i = 1; i < n - k; i++) {
            newTail = newTail.next;
        }
        // 4. 重组链表
        ListNode newHead = newTail.next;
        newTail.next = null;
        tail.next = head;
        
        return newHead;
    }
}