/**
 * 算法链表结构
 */
public class ListNode {
     public int val;
     public ListNode next;
     ListNode() {}
     public ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    public static ListNode build(Integer... obj){
         return build(Arrays.asList(obj));
    }
    public static ListNode build(List<Integer> arr){
         if(arr.isEmpty()){
             return null;
         }

        ListNode listNode = new ListNode(arr.get(0));
         ListNode cur=listNode;
        for (int i = 1; i < arr.size(); i++) {
            cur.next=new ListNode(arr.get(i));
            cur=cur.next;
        }
        return listNode;
    }

    /**
     * 构造成环的链表
     * @param index 成环的位置
     * @param obj 链表节点内容
     * @return
     */
    public static ListNode buildCycle(Integer index,Integer... obj){
        List<Integer> arr = Arrays.asList(obj);
        ListNode listNode = new ListNode(arr.get(0));
        ListNode cur=listNode;
        ListNode pos=null;
        for (int i = 1; i < arr.size(); i++) {
            if(index==i){
                pos=cur;
            }
            cur.next=new ListNode(arr.get(i));
            cur=cur.next;
        }
        cur.next=pos;
        return listNode;
    }

    public void print(){
         ListNode node=this;
         while(node!=null){
             System.out.print(node.val+",");
             node=node.next;
         }
        System.out.println();
    }
 }

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode old=new ListNode(-1,head),result=old;
        ListNode slow=head,fast=head;
        while(n>0){
            fast=fast.next;
            n--;
        }
        while(fast!=null){
            old=slow;
            slow=slow.next;
            fast=fast.next;
        }
        old.next=slow!=null?slow.next:null;
        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;
    }
}