/**
 * @author wuze
 * @desc ...
 * @date 2021-03-11 16:58:04
 */
/*
有 N 个程序猿围成一圈顺序循环报数，从第一个猿开始报数（从 1 到 4 报数，猿都是顺序排列成一圈的），
凡报到 4 的猿退出圈子，问最后留下的是原来第几号的那位。
 */

public class kaniu_2 {
    public static void main(String[] args) {
        //指定有多少个程序员
        int n=10;
        //创建一个有n个节点的环形链表
        CircleLinkedList circleLinkedList = new CircleLinkedList(n);

        //假设从1号程序员开始报数 startNo=1
        int exitNum=circleLinkedList.judgeExit(n,1);
        System.out.println(exitNum);
    }


    static class ListNode{
        //编号
        int no;
        //下一节点
        ListNode next;

        //构造节点
        ListNode(int no){
            this.no=no;
        }

        ListNode getNextNode(){
            return next;
        }
        void setNextNode(ListNode nextNode){
            this.next=nextNode;
        }

        int getNo(){
            return no;
        }

    }

    //环形链表
    static class CircleLinkedList{
        ListNode first=null;
        ListNode cur=null;//辅助结点
        //构造一个环形链表（n个人）
        CircleLinkedList(int n){
            ListNode node;
            if(n<1){
                return ;
            }else{
                //添加节点，编号为i（从1开始）
                for (int i=1;i<=n;i++){
                    //第一个节点，独自成环
                    if(i==1){
                        first= new ListNode(i);
                        first.setNextNode(first);
                        cur=first;
                    }else{
                        //创建新结点
                        node=new ListNode(i);
                        //将node插入（用cur在遍历添加链表）
                        cur.setNextNode(node);
                        //连接成环形链表
                        node.setNextNode(first);
                        //cur指示指针向后移动
                        cur=cur.getNextNode();
                    }
                }
            }

        }

        /*
            n：表示有几个程序员
        	startNo：表示从第几个孩子开始数
         */
        int judgeExit(int n,int startNo) {
            //创建一个辅助指针（用来遍历）
            ListNode help=first;

            //数据校验
            if(first==null || startNo <1){
                return -1;
            }

            //先让辅助指针指向环形链表的最后（也就是help结点是first的前一个节点，以便待会连接成环形链表）
            while(true){
                if(help.getNextNode()==first){
                    break;
                }
                help=help.getNextNode();
            }

            //报数前，移动到startNo位置的前一个位置（移动startNo-1次）
            for(int j=0;j<startNo-1;j++){
                //让开始位置的节点为first结点
                first=first.getNextNode();
                help=help.getNextNode();
            }

            //循环操作
            while(true){
                if(help==first){//说明环中只有一个点，这个人就是最后一个
                    break;
                }

                //因为报数到4退出，所以先移动3次
                for(int i=0;i<3;i++){
                    first=first.getNextNode();
                    help=help.getNextNode();
                }
                //此时first.getNo()程序员退出

                first=first.getNextNode();
                //剔除掉此时first指向的节点
                //让help成为first前一个节点的原因是为了连接成环形链表
                help.setNextNode(first);
            }


            //最后只剩一个节点
            return first.getNo();

        }
    }
}