// @Title: 旋转链表 (Rotate List)
// @Author: qisiii
// @Date: 2024-05-21 23:24:21
// @Runtime: 0 ms
// @Memory: 41.3 MB
// @comment: 
// @flag: 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null||k==0){
            return head;
        }
            ListNode copy=head;
            int n=0;
            while(copy!=null){
                n++;
                copy=copy.next;
            }
            if(n==k){
                return head;
            }else{
                k=k%n;
            }
            if(head==null||k==0){
            return head;
        }
            ListNode reverse=rotate(head,n);
            ListNode left=rotate(reverse,k);
            ListNode temp=left;
            int other=n-k;
            ListNode pre=null;
            while(k>0){
                pre=left;
                left=left.next;
                k--;
            }
            ListNode right=rotate(left,other);
            pre.next=right;
            return temp;
        }

        private ListNode rotate(ListNode head,int m){
            ListNode result=new ListNode(-1,head);
            ListNode cur=head,prev=result;
            ListNode next=null;
            while(m>1){
                next=cur.next;
                cur.next=next.next;
                next.next=prev.next;
                prev.next=next;
                m--;
            }
            return result.next;
        }
}

// @Title: 旋转链表 (Rotate List)
// @Author: qisiii
// @Date: 2024-09-25 15:16:48
// @Runtime: 0 ms
// @Memory: 41.6 MB
// @comment: 一种只需要遍历O(n+k)次的解法
// @flag: GREEN
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 * 遍历次数最多O(n+k)次
 * 当k<n，通过双指针去找到第k个节点和第n个节点，返回结果是k.next，让n.next=head即可
 * 当k>n，此时双指针中fast走到最后，只需要让slow指针再走n-k步即可，当然n=n%k，这里面n正好是k的倍数的时候，是不用旋转的，因此直接return head;
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(k==0||head==null){
            return head;
        }
        int count = 0;
        ListNode fast = head;
        ListNode slow = head;
        //当k<=length的时候，通过让fast先走k步找到两个链表的尾结点，如例1中的3和5
        while (fast.next != null) {
            fast = fast.next;
            if (count >= k) {
                slow = slow.next;
            }
            count++;
        }
        //当k>length的时候，此时fast已经处于尾部，接下来只需要让slow移动(length-k%length)步就可以了，
        //还是拿例1距离，假如n为7，length是5，此时length-2就是slow要走的步数
        if (slow==head) {
            int length=count+1;
            //如果k刚好是length的倍数，那就不用旋转
            if(k%length==0){
                return slow;
            }
            count=length-k%length-1;
            while(count>0){
                slow=slow.next;
                count--;
            }
        }
        ListNode result = slow.next;
        fast.next = head;
        slow.next = null;
        return result;
    }
}