应用场景

n 个小孩标号，逆时针站一圈。从 k 号开始，每一次从当前的小孩逆时针数 m 个，然后让最后这个小孩出列。不断循环上述过程，直到所有小孩出列，由此产生出一个队列编号。

提示

用一个不带头节点的循环链表来处理 Josephu 问题：先构成一个有 n 个节点的单循环链表，然后从 k 节点起从 1 开始计数，记到 m 时对应的节点从链表中删除，然后从下一个节点从 1 开始计数，直到最后一个节点从链表中删除算法结束

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

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

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

//添加节点，构建成一个环形链表public void addBoy(int nums) {  //nums代表添加的节点的个数//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;  //让curBoy指向第一个小孩} else {curBoy.setNext(boy);boy.setNext(first);curBoy = boy;}}}

遍历环形链表

1.先让一个辅助变量 curBoy 指向 first 节点

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

//遍历当前环形链表public void showBoy() {//判断链表是否为空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();  //让curBoy后移}}

根据用户输入，生产一个小孩出圈的顺序

1.需要创建一个辅助指针 helper ，事先应该指向环形链表的最后这个节点

2.在报数前，先让 first 和 helper 移动 k-1 次

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

4.这时就可以将 first 指向的小孩节点出圈

first = first.next;

helper.next = first

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

//根据用户输入，计算小孩出圈顺序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) {break;}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 - 1for (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("最后留在圈中的小孩编号%d\n", first.getNo());}

Josephu 问题的解决以及测试

public class Josephu {public static void main(String[] args) {//测试一把，看看构建环形链表和遍历是否okCircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();circleSingleLinkedList.addBoy(5);circleSingleLinkedList.showBoy();System.out.println();//测试一把小孩出圈是否正确circleSingleLinkedList.countBoy(1,2,5);System.out.println();}
}//创建一个环形的单向链表
class CircleSingleLinkedList {//创建一个first节点，当前没有编号private Boy first = new Boy(-1);//添加节点，构建成一个环形链表public void addBoy(int nums) {  //nums代表添加的节点的个数//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;  //让curBoy指向第一个小孩} else {curBoy.setNext(boy);boy.setNext(first);curBoy = boy;}}}//遍历当前环形链表public void showBoy() {//判断链表是否为空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();  //让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) {break;}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 - 1for (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("最后留在圈中的小孩编号%d\n", first.getNo());}
}//创建一个Boy类，表示一个节点
class Boy{private int no;  //编号private Boy next;  //指向下一节点，默认为nullpublic 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;}
}