1、约瑟夫问题（丢手绢问题）：
- N个小孩围成一个圈，标号为1到N；
- 从编号为m的小孩开始报数，报到第k(1 <= k <= n)个小孩时，该小孩退出游戏；
- 然后下一个小孩继续从1开始报数，数到第k个小孩时，该小孩退出游戏；
- 如此循环，剩下最后一个小孩是胜利者。
2、JAVA代码
package DataStructures.LinkedList;/*** @author yhx* @date 2020/09/16*/
public class Josephu {public static void main(String[] args) {//创建环形链表CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();circleSingleLinkedList.addBoy(5);//打印环形链表中的数据circleSingleLinkedList.showBoy();//测试出圈操作circleSingleLinkedList.countBoy(1, 2, 5);}
}/*** 创建一个环形单向链表*/
class CircleSingleLinkedList {private Boy first = new Boy(-1);/*** 添加小孩节点，构成环形链表** @param nums 小孩的个数*/public void addBoy(int nums) {//对num做一个数据校验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指向第一个小孩curBoy = first;} else {//辅助指针curBoy的next指向新创建的小孩节点BoycurBoy.setNext(boy);//新创建小孩节点Boy的next指向第一个小孩boy.setNext(first);//curBoy后移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());//如果辅助指针的next指回第一个小孩，说明遍历完成if (curBoy.getNext() == first) {break;}//curBoy后移curBoy = curBoy.getNext();}}/*** 计算小孩的出圈顺序** @param starNo 从第几个小孩开始数数(m)* @param countNum 数几下(k)* @param nums 总共有几个小孩(N)*/public void countBoy(int starNo, int countNum, int nums) {//先对数据校验if (first == null || starNo < 1 || starNo > nums) {System.out.println("参数输入有误，请重新输入");return;}//创建辅助指针，事先指向环形链表的最后节点Boy helper = first;while (helper.getNext() != first) {helper = helper.getNext();}//小孩报数前，先让first和helper移动m-1次for (int i = 0; i < starNo - 1; i++) {first = first.getNext();helper = helper.getNext();}//小孩报数时，让first和helper同时移动k-1次//当helper等于first时，说明圈中只有一个人while (helper != first) {for (int j = 0; j < countNum - 1; j++) {first = first.getNext();helper = helper.getNext();}//移动完成后，first指向的节点，就是要出圈小孩的节点System.out.printf("小孩%d出圈\n", first.getNo());//出圈操作first = first.getNext();helper.setNext(first);}System.out.printf("最后一个小孩是%d号，本轮游戏他获胜 \n", helper.getNo());}
}/*** 创建一个Boy类，表示一个节点* no 编号* next 指向下一个节点，默认null*/
class Boy {private final int no;private Boy next;public Boy(int no) {this.no = no;}public int getNo() {return no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}
}
3、运行结果
小孩的编号1
小孩的编号2
小孩的编号3
小孩的编号4
小孩的编号5 小孩2出圈
小孩4出圈
小孩1出圈
小孩5出圈
最后一个小孩是3号，本轮游戏他获胜