环形链表以及约瑟夫问题

Java编写环形单向链表

单向环形链表，跟单链表的唯一区别就是尾结点会指向头节点，形成一个循环(循环)链表。
使用 Java 实现单向环形链表的添加和遍历方法。

思路：
先创建第一个节点, 让 first的next指针指向该节点，并形成环形
后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.
遍历环形链表

先让一个辅助指针(变量) curBoy，指向first节点
然后通过一个while循环遍历 该环形链表即可 curBoy.next == first 结束
根据用户的输入，生成一个小孩出圈的顺序

代码实现

//创建一个环形的单向链表
class CircleSingleLinkedList {
    //创建一个first节点，当前没有编号
    private Boy first = null;
    //添加小孩节点，构件成一个环形的链表
    public void addBoy(int nums) {
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        //帮助构建环形链表
        Boy curBoy = null;
        //使用for循环创建我们的环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号，创建小孩节点
            Boy boy = new Boy(i);
            //如果是第一个小孩
            if (i == 1) {
                first = boy;
                first.setNext(first);
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    //遍历当前的环形链表
    public void showBoys() {
        //判断链表是否为空
        if (first == null) {
            System.out.println("没有任何小孩");
            return;
        }
        //因为first不能动，因此我们仍然使用一个辅助指针完成遍历
        Boy curBoy = first;
        do {
            System.out.println("小孩编号：" + curBoy.getNo());
            curBoy = curBoy.getNext();
        } while (curBoy != first);
    }
}

/**
 * 创建一个Boy，表示一个节点
 */
class Boy {
    private int no;
    private Boy next;

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

    public Boy(int no, Boy next) {
        this.no = no;
        this.next = next;
    }
	//set/get省略了...
	
    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}

约瑟夫问题

思路：用一个辅助指针，指向最后一个结点，当最后一个结点等于首个节点时，说明只剩下最后一个人了。

/**
 * 根据用户的输入，计算小孩除权的顺序
 *
 * @param startNo  表示从第几个小孩开始数数
 * @param countNum 表示数几下
 * @param nums     表示最初由多少小孩在圈中
 */
public void countBoy(int startNo, int countNum, int nums) {
    //先对数据进行校验
    if (first == null || startNo < 1 || startNo > nums) {
        System.out.println("参数输入有误，请重新输入");
        return;
    }
    Boy helper = first.getNext();
    //使辅助指针helper指向最后一个小孩
    while (helper.getNext() != first) {
        helper = helper.getNext();
    }
    //小孩报数前，先让 first 和 helper移动 startNo - 1 次
    for (int i = 0; i < startNo - 1; i++) {
        first = first.getNext();
        helper = helper.getNext();
    }
    //当小孩报数使，先让 first 和 helper 指针同时的移动 countNum  - 1 次，然后出圈
    //这里是一个循环操作，直到圈中只有一个节点

    //当 helper == first 使 表示只有一个节点
    while (helper != first) {
        //让 first 和 helper 指针同时的移动 countNum -1 次
        for (int i = 0; i < countNum - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        System.out.println("小孩"+first.getNo()+"出圈");
        first = first.getNext();
        helper.setNext(first);
    }
    System.out.println("最后留着圈中的小孩"+first.getNo());
}