约瑟夫(环形链表)

/**
 * @author 缪广亮
 * @version 1.0
 */
class Joseph {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.list();
    }

}

//Boy的节点类
class Boy {
    public int no;//编号
    public Boy next;
    public Boy(int no){
        this.no=no;
        this.next=null;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}
//创建一个环形的单向链表
class CircleSingleLinkedList{
//    创建一个first结点，当前没有编号
    private Boy first=new Boy(-1);
//    添加小孩结点，构建成一个环形链表
    public void addBoy(int nums){
//        nums校验
        if (nums<1){
            System.out.println("nums不能小于1~~~");
            return;
        }
        Boy curBoy=null;//辅助指针，帮助构建环形链表
//        使用for来创建我们的环形链表
        for (int i = 1; i <=nums ; i++) {
//            根据编号创建小孩节点
            Boy boy = new Boy(i);
//            如果是第一个小孩
            if (i==1){
                first=boy;
                first.next=first;//构成一个环
                curBoy=first;//让curBoy指向第一个小孩
            }else {
                curBoy.next=boy;//
                boy.next=first;//
                curBoy=boy;
            }
        }
    }
//    遍历环形链表
    public void list(){
        if (first==null){
            System.out.println("环形链表为空,无小孩");
            return;
        }
//        first不能动，所以需要一个辅助指针完成遍历
        Boy curBoy=first;
        while (true){
            System.out.printf("小孩的编号%d \n",curBoy.no);
            if (curBoy.next==first)//遍历完成
                break;
            curBoy=curBoy.next;
        }
    }
}