1. 单向环形链表介绍

正常的单链表每个节点顺次连接，最后一个节点指向NULL，如下图所示。

而带环链表的最后一个节点不再指向 NULL 了，指向的是前面任意一个节点，以此形成带环链表，并一直循环下去，如下图所示。

1.1 Josephu(约瑟夫)问题

Josephu(约瑟夫)问题为：设编号1、2、3、…、n-1、n的n个人围坐一圈，约定编号为 k(1<=k<=n)的人从1开始报数，数到 m 的那个人出列，它的下一位又从1开始报数，数到 m 的那个人出列，它的下一位又从1开始报数数到 m 的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表处理Josephu(约瑟夫)问题。

先构成构成一个有n个节点的单循环链表，然后由 k 节点起从1 开始计数，计到 m 时，对应节点从链表中删除，然后再从被删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除，算法结束。

Josephu(约瑟夫)问题示意图如下。

假设 n=5，既有5个人。k=1，从第1个人开始报数。m=2，数2下。

构建一个单向的环形链表思路：

（1）先创建第一个节点，让 first 指向该节点，并形成环形。

（2）后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。

遍历环形链表：

（1）先让一个辅助指针（变量），指向 first 节点；

（2）然后通过一个 while 循环遍历该环形链表即可 curBoy.next == first 结束；

代码如下：

/**
 * 单向环形链表
 */
public class Josefu {
    public static void main(String[] args) {
        // 测试  构建环形列表
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);

        // 测试 遍历
        circleSingleLinkedList.show();
    }
}

// 创建一个环形的单向链表
class CircleSingleLinkedList {
    // 创建一个 first 节点
    private Boy first = null;

    // 添加小孩节点，构建成一个环形的链表
    public void addBoy(int nums) {
        // nums 做一个数据校验
        if (nums < 1) {
            System.out.println("nums 的值不正确");
            return;
        }

        // 辅助指针
        Boy curBoy = null;
        // 使用循环创建环形链表
        for (int i = 1; i <= nums; i++) {
            // 根据编号创建节点
            Boy boy = new Boy(i);
            // 如果是第一个节点
            if (i == 1) {
                first = boy;
                first.setNext(boy);
                // 让curBoy指向第一个节点
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first);
                // 指针后移
                curBoy = boy;
            }
        }
    }


    // 遍历当前的环形链表
    public void show() {
        // 判断链表是否为空
        if (first == null) {
            System.out.println("链表为空");
            return;
        }

        // first 不能动，定义一个辅助指针进行遍历
        // 辅助指针
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的编号【%d】\n", curBoy.getNo());
            if(curBoy.getNext() == first){
                // 说明已经遍历完毕
                break;
            }
            // 指针后移
            curBoy = curBoy.getNext();
        }
    }
}

// 定义一个节点
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;
    }
}

根据用户的输入，生成一个小孩出圈的顺序思路：

（1）需求创建一个辅助指针（变量）helper，事先应该指向环形链表的最后这个节点；

（2）小孩报数前，先让 first 和 helper 移动 k-1 次

（3）当小孩报数时，让 first 和 helper 指针同时移动 m-1 次；

（4）这是就可以将 first 指向的小孩节点出圈。

first = first.next;

helper.next = first;

原来 first 指向的节点就没有任何引用，会被垃圾回收。

代码示例：

/**
 * 单向环形链表
 */
public class Josefu {
    public static void main(String[] args) {
        // 测试  构建环形列表
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(55);

        // 测试 遍历
        circleSingleLinkedList.show();

        // 测试小孩出圈
        circleSingleLinkedList.countBoy(1,2,55);
    }
}

// 创建一个环形的单向链表
class CircleSingleLinkedList {
    // 创建一个 first 节点
    private Boy first = null;

    // 添加小孩节点，构建成一个环形的链表
    public void addBoy(int nums) {
        // nums 做一个数据校验
        if (nums < 1) {
            System.out.println("nums 的值不正确");
            return;
        }

        // 辅助指针
        Boy curBoy = null;
        // 使用循环创建环形链表
        for (int i = 1; i <= nums; i++) {
            // 根据编号创建节点
            Boy boy = new Boy(i);
            // 如果是第一个节点
            if (i == 1) {
                first = boy;
                first.setNext(boy);
                // 让curBoy指向第一个节点
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first);
                // 指针后移
                curBoy = boy;
            }
        }
    }


    // 遍历当前的环形链表
    public void show() {
        // 判断链表是否为空
        if (first == null) {
            System.out.println("链表为空");
            return;
        }

        // first 不能动，定义一个辅助指针进行遍历
        // 辅助指针
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的编号【%d】\n", curBoy.getNo());
            if (curBoy.getNext() == first) {
                // 说明已经遍历完毕
                break;
            }
            // 指针后移
            curBoy = curBoy.getNext();
        }
    }

    /**
     * 根据用户的输入，计算出圈的顺序
     *
     * @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;
        // 将 helper 指针指向最后一个节点
        while (true) {
            // 说明 helper 指向最后一个节点
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        // 小孩报数前，先让 first 和 helper 移动 k-1 次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        // 当小孩报数时，让 first 和 helper 指针同时移动 m-1 次，然后出圈
        while (true) {
            if (helper == first) {
                // 说明圈中只有一个节点
                break;
            }
            // 让 first 和 helper 指针同时移动 countNum-1
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }

            // first 指向的节点就是要出圈的节点
            System.out.printf("小孩【%d】出圈\n", first.getNo());
            // 将 first 指向的小孩出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号【%d】" , first.getNo());

    }
}

// 定义一个节点
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;
    }
}