总目录：地址如下看总纲
1、什么是约瑟夫问题
约瑟夫问题其实也是一个游戏(丢手绢)，也称为约瑟夫环。
规则很简单：就是有一群小鬼围起来(例5个)成一个圈，先从第一个小鬼报数 n，以第一个小鬼的第n 个小鬼，
既出列，出列的 第 n 个小鬼的后面一个 继续报数 n ，依次类推直到所有小鬼都离开这个圈中
image.png
解决方案：可以使用单向环形链表
2、单向环形链表的构建和遍历分析
image.png
1、构建一个单向的环形链表思路
(1). 先创建第一个节点, 让 first 指向该节点，并形成环形
(2). 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可
2、遍历环形链表
(1). 先让一个辅助指针(变量) curKid，指向first节点
(2). 然后通过一个while循环遍历 该环形链表即可 curKid.next == first 结束
3、单向环形链表抓鬼
image.png
根据用户的输入，生成一个小鬼出圈的顺序（方法：countKid）
n = 5 , 即有5只鬼
k = 1, 从第一个小鬼开始报数
m = 2, 数2下(包括它自己也得数)
- 需求创建一个辅助指针(变量) helper (讨债鬼), 事先应该指向环形链表的最后这个节点.
2.小鬼报数前，先让 first 和 helper 移动 k - 1次- 当小鬼报数时，让first 和 helper 指针同时 的移动 m - 1 次
- 这时就可以将first 指向的小鬼节点 出圈
first = first .next
helper.next = first
原来first 指向的节点就没有任何引用，就会被回收
helper (讨债鬼)：作用就是一直跟在first后面，得到first不行了就把锁链套在下一个first脖子，直达所有都套死
出圈的顺序
2->4->1->5->3
3、代码实现
package com.kk.datastructure.linkedlist.josepfu;
/**
* title: 约瑟夫问题--单向环形链表
* @author 阿K
* 2020年11月28日 下午7:56:21
*/
public class Josepfu {
public static void main(String[] args) {
// 测试一把构建环形链表，和遍历
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addKid(5);// 加入5个小鬼节点
circleSingleLinkedList.showKid();
// 测试一把小鬼出圈
circleSingleLinkedList.countKid(1, 2, 5); // 2->4->1->5->3
}
}
//创建一个环形的单向链表
class CircleSingleLinkedList {
// 创建一个first节点,当前没有编号
private Kid first = null;
// 添加小鬼节点，构成一个环形链表(并非一个个添加，而是初始化个数)
public void addKid(int nums) {
if (nums < 1) {
System.out.println("数量错误，无法构建环形");
return;
}
// 辅助指针，帮助构建环形链表
Kid curKid = null;
// 使用for来创建我们的环形链表
for (int i = 1; i <= nums; i++) {
// 根据编号，创建小鬼节点
Kid kid = new Kid(i);
// 如果是第一个小鬼
if (i == 1) {
first = kid;
first.setNext(first);// 构成环
curKid = first; // 让curKid指向第一个小鬼
} else {
curKid.setNext(kid);// 此时的辅助是指向 first,它后面则指向 新节点(编号 2...)
kid.setNext(first); // 构成环
curKid = kid; // 此时curKid 指向第二个小鬼....
}
}
}
// 遍历当前环形链表
public void showKid() {
// 判空
if (first == null) {
System.out.println("没有任何小鬼~~");
return;
}
// 因为first不能动，因此我们仍然使用一个辅助指针完成遍历
Kid curKid = first;
while (true) {
System.out.printf("小鬼的编号 %d \n", curKid.getNo());
if (curKid.getNext() == first) {
// 已经遍历结束
break;
}
// 后移
curKid = curKid.getNext();
}
}
/**
* 开始抓鬼
*
* @param startNo 表示从第几个小鬼开始数数
* @param countNum 表示每次数了几只小鬼(报数几)
* @param nums 表示最初圈内的总鬼数
*/
public void countKid(int startNo, int countNum, int nums) {
// 数据校验
if (first == null || startNo < 1 || startNo > nums) {
System.out.println("参数输入有误， 请重新输入");
return;
}
// 创建辅助指针，讨债鬼，作用催命
Kid helper = first;// 初始化自己套自己，因为圈内目前就一个
// 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
while (true) {
if (helper.getNext() == first) {
// 已经到最后一个
break;
}
// 后移
helper = helper.getNext();
}
// 考虑到 可能不是 k=1的情况：
// 小鬼报数前，先让 first 和 helper 移动 k - 1(startNo - 1)次
for (int j = 0; j < startNo - 1; j++) {
first = first.getNext();
helper = helper.getNext();
}
// 当小鬼报数时，让first 和 helper 指针同时 的移动 m - 1 次(countNum -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); // 讨债鬼的绳索套在了新frist脖子上
}
System.out.printf("最后留在圈中的小鬼编号%d \n", first.getNo());
}
}
//创建一个Kid类，表示一个节点
class Kid{
private int no;// 编号
private Kid next;// 指向下一个节点
public Kid(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Kid getNext() {
return next;
}
public void setNext(Kid next) {
this.next = next;
}
}
