环形链表解决Josephu环

package linkedlist;
//单向环形链表完成Josephu问题
public class Josephu {
    public static void main(String[] args) {

        //测试一把，看构建环形链表，黑暗里是否oK
        CircleSinglelinkedList circleSinglelinkedList = new CircleSinglelinkedList();
        circleSinglelinkedList.addBoy(125);//加入5个小孩节点
        circleSinglelinkedList.showBoy();

        //测试一把小孩是否出圈
        circleSinglelinkedList.countBoy(10,20,125);
    }
}

//创建一个环形的单向链表
class CircleSinglelinkedList{
    //创建一个first节点，当前没有编号
    private Boy first = new Boy(-1);//private Boy first = null;也可以
    //添加小孩节点，构建成一个环形链表
    public void addBoy(int nums){//nums代表一共添加几个小孩
        //对nums做一个数据校验
        if(nums < 1){
            System.out.println("nums的值不正确");
            return;
        }

        Boy curBoy = null;//辅助变量(指针)，帮助创建环形链表
        //curBoy使用来表示添加到了第几个节点，即之后应该往哪个节点后添加新的节点
        //使用for循环创建环形链表
        for (int i = 1;i <= nums;i++){
            //根据编号，创建小孩节点
            Boy boy = new Boy(i);
            //如果是第一个小孩
            if(i == 1){
                first = boy;
                first.setNext(first);//构成一个环
                curBoy = first;//让curBoy指向第一个小孩
            }else{
                curBoy.setNext(boy);//这行代码意义何在？先让当前的节点的next指向新添加进来的节点？
                boy.setNext(first);//将新添加的节点的next指向第一个节点
                curBoy = boy;//把curBoy这个辅助指针指向新添加的(最后)一个节点
            }
        }
    }

    //遍历当前的环形链表
    public void showBoy(){
        //判断链表是否为空
        if(first == null){
            System.out.println("没有任何小孩");
        }

        //因为first不能动，因此我们仍然使用一个辅助指针完成遍历
        Boy curBoy = first;
        while(true){
            System.out.printf("小孩的编号%dn",curBoy.getNo());
            if(curBoy.getNext() == first){//说明已经遍历完成
                break;
            }
            curBoy = curBoy.getNext();//相当于是让curBoy后移
        }

    }

    //根据用户的输入，计算出小孩出圈的顺序

    
    public void countBoy(int startNo,int countNum,int nums){
        //先对数据进行校验
        if(first == null || startNo < 1 || startNo > nums){
            System.out.println("参数输入有误，请重新输入");
            return;
        }

        //创建辅助指针，帮助完成小孩出圈
        Boy helper = first;
        //需要创建一个辅助变量(指针)helper，事先应该指向环形链表的最后的这个节点
        while(true){
            if(helper.getNext() == first){//说明helper指向了最后一个小孩节点
                break;
            }else{
                helper = helper.getNext();
            }
        }

        //小孩报数前，先让first和helper移动k - 1次
        for(int j = 0;j < startNo - 1;j++){
            first = first.getNext();
            helper = helper.getNext();
        }

        //开始报数
        //当小孩报数时，让first和helper指针同时移动 m - 1次，然后出圈
        //这里是一个循环操作，直到圈中之后一个节点
        while(true){
            if(helper == first){//说明圈中只有一个节点
                break;
            }
            //让first 和 helper同时移动countNum - 1次,然后出圈
            for(int j = 0;j < countNum - 1;j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //这是first指向的节点，就是要出圈的小孩节点
            System.out.printf("小孩%d出圈n",first.getNo());
            //这时，将first指向的小孩节点出圈
            first = first.getNext();
            helper.setNext(first);//
        }

        System.out.printf("最后留在圈中的小孩编号是：%dn",first.getNo());

    }
}

//创建一个Boy类，表示一个节点
class Boy{
    private int no;
    private Boy next;//指向下一个节点，默认为空

    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}