1.什么约瑟夫问题：

一群小朋友在一起丢手绢，有n个小朋友选定一个小朋友作为第一个人，开始报数，第一个小朋友数1，当报到第m个数的时候，那么那个人出局,然后他的下一个小朋友再次从1开始报数，再次数到第m个数，再次出局，如此循环，直到剩下1个小朋友

2.我们使用单向循环链表来解决这个问题

3.我们创建一个循环单链表的节点类

//创建一个节点类 class BoyNode{ private int no;//编号 private BoyNode next; //指向下一个节点，默认是空 public BoyNode(int no) { this.no = no; } @Override public String toString() { return "BoyNode{" + "no=" + no + '}'; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public BoyNode getNext() { return next; } public void setNext(BoyNode next) { this.next = next; } }

4. 创建循环单链表的类以及展示

public class Josepfu { public static void main(String[] args) { //测试构建环形链表，和遍历是否ok CircleSingleLinkedList list = new CircleSingleLinkedList(); list.addBoy(5); //加入5个小孩节点 list.showBoy(); //测试一把小孩出圈，是否正确 list.countBoy(2,2,5); //35214 } } //创建一个环形的单向链表 class CircleSingleLinkedList{ //创建一个first节点，当前没有编号 private BoyNode first = new BoyNode(-1); //添加小孩节点，构建成一个环形链表 public void addBoy(int nums){ //nums == 整个环形列表有几个节点 //nums 做一个简单的数据校验 if(nums<1){ System.out.println("nums的值不正确"); return; } BoyNode curBoy = null;// 辅助节点，帮助构建环形链表 //使用for循环来创建环形单向链表 for (int i = 1; i <= nums ; i++) { //根据编号创建小孩节点 BoyNode boy = new BoyNode(i); //如果是第一个小孩 if (i==1){ first = boy; curBoy = first; //让curBoy指向第一个小孩 first.setNext(first); //等价于 first = first.next }else{ //其他小孩 curBoy.setNext(boy); //等价于curBoy.next = boy boy.setNext(first); //等价于 boy.next = first curBoy = boy; } } } //遍历当前环形链表 public void showBoy(){ //判断是不是空的链表 if (first == null){ System.out.println("链表为空"); return; } //因为first不能动，所以使用辅助变量 BoyNode curBoy = first; while (true){ System.out.printf("小孩的编号为%d\n",curBoy.getNo()); if (curBoy.getNext()==first){ //说明遍历完毕 break; } curBoy = curBoy.getNext(); } } //根据用户的输入，计算出出圈的人 // startNo 表示从第几个小孩开始数数，countNum表示一次数几个，nums表示最初有几个小孩 public void countBoy(int startNo,int countNum,int nums){ //先对数据进行校验 if (first==null||startNo<1||startNo>nums){ System.out.println("你的参数输入有问题，请重新输入"); return; } //创建一个辅助指针，帮助完成小孩出圈 BoyNode helper = first; //需求创建一个辅助指针helper，事先应该指向环形链表的最后一个节点 while (true){ if (helper.getNext()==first){ //说明这个helper指向了最后一个小孩节点 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-1次，然后出圈 for (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",helper.getNo()); } } //创建一个节点类 class BoyNode{ private int no;//编号 private BoyNode next; //指向下一个节点，默认是空 public BoyNode(int no) { this.no = no; } @Override public String toString() { return "BoyNode{" + "no=" + no + '}'; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public BoyNode getNext() { return next; } public void setNext(BoyNode next) { this.next = next; } }