- 设编号为1，2，…，n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，他的下一位又从1开始数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
- 用一个不带头节点的循环链表来处理Josephu 问题：先构成一个又n个节点的单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后再从被删除的节点的下一个节点又开始从1开始计数，直到最后一个节点从链表中删除，算法结束
- 先创建第一个节点，让first 指向该节点，并形成环形
- 后面当我们每创建一个新的节点，就把该节点加入到已有的环形链表中即可
- 先让一个辅助指针cur，指向first节点
- 然后通过一个while 循环遍历该环形链表即可。cur.next == first结束
- 方法1：创建一个辅助节点temp，初始化在first 指针后面，每次让first 指在需要出圈的节点，然后进行操作
- 方法2：只用一个first 指针，使其每次指在需要出圈节点的前一个节点，然后进行操作
下面代码主要利用方法2
public static void JosephuRing(int sum,int k,int m){
//k,sum和m取值校验
//即k的值小于等于sum且大于0
//m的值大于1，虽然理论上可以取1，但我们认为这是毫无意义的，就相当于将first放在k上依次遍历
if(k > sum || k <= 0 || m <= 1){
System.out.println("~~~数据输入有误，请输入正确的数据!!!~~~");
return;
}
CircleSingleLinkedList josephu = new CircleSingleLinkedList();
josephu.addBoy(sum);
//将孩子出圈的顺序存入数组中
int[] arr = new int[sum];
//根据需求，环形链表中的first节点对于本问题无影响
//首先将first指针指向第k个人
josephu.setFirst(josephu.find(k));
System.out.printf("移动到第 %d 个人的位置：",k);
josephu.showCircle();
Boy temp = josephu.getFirst();
//从第k个人开始数（m-1）个数
//由于sum个人，所以一共只需要循环sum次
for(int i = 0; i < sum; i++){
for(int j = 2; j < m; j++){
//将first节点向后移动一位，直到移动在数(m - 1)个数的时候
josephu.setFirst(josephu.getFirst().getNext());
}
if(josephu.getFirst().getNext() == josephu.getFirst()){
arr[i] = josephu.getFirst().getNo();
josephu.setFirst(null);
System.out.printf("~第 %d 次后，所有人都已经出圈~n",i + 1);
//输出孩子出约瑟夫环顺序
System.out.println("孩子们的出圈顺序为：");
for(int count = 0; count < arr.length; count ++){
System.out.printf(" => %d",arr[count]);
}
return;
}
arr[i] = josephu.getFirst().getNext().getNo();
//要出圈的人就是first节点的下一个节点
josephu.getFirst().setNext(josephu.getFirst().getNext().getNext());
josephu.setFirst(josephu.getFirst().getNext());
//输出每次出圈后的情况
System.out.printf("第 %d 次出圈后顺序：",i+1);
josephu.showCircle();
}
}
完整代码（附环形链表创建及增删改查）
package com.crisp.LinkedList;
public class Josephu {
public static void main(String[] args) {
//测试约瑟夫环
JosephuRing(10,5,2);
}
public static void JosephuRing(int sum,int k,int m){
//k,sum和m取值校验
//即k的值小于等于sum且大于0
//m的值大于1，虽然理论上可以取1，但我们认为这是毫无意义的，就相当于将first放在k上依次遍历
if(k > sum || k <= 0 || m <= 1){
System.out.println("~~~数据输入有误，请输入正确的数据!!!~~~");
return;
}
CircleSingleLinkedList josephu = new CircleSingleLinkedList();
josephu.addBoy(sum);
//将孩子出圈的顺序存入数组中
int[] arr = new int[sum];
//根据需求，环形链表中的first节点对于本问题无影响
//首先将first指针指向第k个人
josephu.setFirst(josephu.find(k));
System.out.printf("移动到第 %d 个人的位置：",k);
josephu.showCircle();
Boy temp = josephu.getFirst();
//从第k个人开始数（m-1）个数
//由于sum个人，所以一共只需要循环sum次
for(int i = 0; i < sum; i++){
for(int j = 2; j < m; j++){
//将first节点向后移动一位，直到移动在数(m - 1)个数的时候
josephu.setFirst(josephu.getFirst().getNext());
}
if(josephu.getFirst().getNext() == josephu.getFirst()){
arr[i] = josephu.getFirst().getNo();
josephu.setFirst(null);
System.out.printf("~第 %d 次后，所有人都已经出圈~n",i + 1);
//输出孩子出约瑟夫环顺序
System.out.println("孩子们的出圈顺序为：");
for(int count = 0; count < arr.length; count ++){
System.out.printf(" => %d",arr[count]);
}
return;
}
arr[i] = josephu.getFirst().getNext().getNo();
//要出圈的人就是first节点的下一个节点
josephu.getFirst().setNext(josephu.getFirst().getNext().getNext());
josephu.setFirst(josephu.getFirst().getNext());
//输出每次出圈后的情况
System.out.printf("第 %d 次出圈后顺序：",i+1);
josephu.showCircle();
}
}
}
//创建一个环形的单向链表
class CircleSingleLinkedList{
//创建一个first节点，当前无编号
private Boy first = null;
//获取头节点
public Boy getFirst() {
return first;
}
//设置头节点位置
public void setFirst(Boy first) {
this.first = first;
}
//添加节点，构建成一个环形的链表
//直接输入参与游戏的人数
public void addBoy(int sum){
//对sum做一个数据校验
if(sum < 1){
System.out.println("游戏人数不正确~");
return;
}
//创建一个辅助指针，帮助创建变量
Boy cur = null;
//使用for循环创建环形链表
for(int i = 1; i <= sum; i++){
//根据编号创建节点
Boy boy = new Boy(i);
//如果是第一个小孩
if(i == 1){
first = boy;
first.setNext(first);//构成环
cur = first;//让cur指向第一个节点
}else{
cur.setNext(boy);
boy.setNext(first);
cur = boy;
}
}
}
//删除节点
public void delete(int delnum){
//判断链表是否为空
if(first == null){
System.out.println("~~~链表为空！！！~~~");
return;
}
//创建两个辅助节点
//一个跟在另一个的后面
//由前一个cur1发现需要删除的节点
//后面的cur2指向发现节点的下一个节点
Boy cur1 = first.getNext();
Boy cur2 = first;
//遍历链表找到需要删除的节点
while(true){
//System.out.println(cur1.getNo());
//System.out.println(cur2.getNo());
if(cur1.getNo() == delnum){
cur2.setNext(cur1.getNext());
if(cur1.getNo() == first.getNo()){
first = cur2.getNext();
}
return;
}
if(cur1.getNo() == first.getNo()){
System.out.println("~没有发现所要删除的节点~");
return;
}
//两个节点均向后移位
cur1 = cur1.getNext();
cur2 = cur2.getNext();
}
}
//查找节点
//由于是一个环形节点
//所以输入值应该为从头节点开始的第num个数，而不是编号值
//注意：first节点应该算作第一个数
public Boy find(int num){
//定义辅助指针，用来在链表中移动
Boy temp = first;
for(int i = num; i > 1; i--){
temp = temp.getNext();
}
return temp;
}
//遍历当前环形链表
public void showCircle(){
//判断是否为空
if(first == null){
System.out.println("链表为空~");
return;
}
//first不可移动，因此使用辅助指针
Boy temp = first;
while(true){
System.out.printf("=> %d ",temp.getNo());
if(temp.getNext() == first){
//最后一个节点
System.out.println();
return;
}
temp = temp.getNext();
}
}
}
//创建一个Boy类，表示一个节点
class Boy{
private int no;//编号
private Boy next;//指向下一个节点
//构造器
public Boy(int no) {
this.no = no;
}
//set方法
public void setNo(int no) {
this.no = no;
}
public void setNext(Boy next) {
this.next = next;
}
//get方法
public int getNo() {
return no;
}
public Boy getNext() {
return next;
}
//重写toString，方便查看
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
该笔记整理自B站BV1E4411H73v，博主稍加整理改进以及排版
