1. Josephu 问题
设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
2. 解决思路
2.1 简述
用一个不带头结点的循环链表来处理 Josephu 问题，先构成一个有 n 个结点的单循环链表。然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除；然后 被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除，算法结束。
2.2 变量
- first，指向编号为 k 的结点
- helper，指向环形链表 first 结点的前 1 个结点
2.3 出圈
- 因为报数从 1 开始，自己本身也算 1 个数，1 到 m 之间共有 m-1 个有向弧；所以 first 要移动 m-1 次，方可到达 [数到 m 的那个人]，helper 结点也移动 m-1 次，它的作用是辅助 first 让第 m 个人出圈。
- 找到第 m 个人，执行代码：
first = first.next; helper.next = first;，而原来 first 指向的结点因没有任何引用指向它而被垃圾回收器回收 - 最后一次
3. 代码实现
public class CircleSingleLinkedList {
// 创建首结点first, 当前还没有编号
private Boy first;
// 构建单向环形链表
public void addBoy(int nums) {
// 1. 对nums做简单数据校验
if (nums < 1) {
System.out.println("nums起码大于1吧");
return;
}
// 辅助变量, 帮助构建环形链表
Boy curBoy = null;
// 2. 创建环形链表
for (int i = 1; i <= nums; i++) {
// 2.1 根据编号 i, 创建Boy结点
Boy boy = new Boy(i);
if (i == 1) { // 2.1.1 如果是第一个Boy
first = boy;
} else {
// 2.1.2 ↓此时curBoy指向的还是上一轮新创建的结点
curBoy.next = boy;
}
// 2.2 新创建的boy的next始终指向first
boy.next = first;
// 2.3 curBoy始终指向最新的创建的boy
curBoy = boy;
}
}
/**
* 根据用户的输入, 计算出小孩出圈的顺序
* @param startNo 从编号为startNo的boy开始数数
* @param countNum 数几下
* @param nums 最初有多少boy在圈中
*/
public void countBoy(int startNo, int countNum, int nums) {
// 0. 数据校验
if (first == null || startNo < 1 || startNo > nums || countNum < 1) {
System.out.println("输入数据有误");
return;
}
/*
* 1. 将 first, helper 移动到 startNo 所确定的位置
* 1.1 helper 应指向 first 的前一个结点
* 1.2 first 应指向编号为 startNo 的结点, 需移动 startNo - 1 次
* 1.3 helper 也得跟着动
*/
Boy helper = first;
while (helper.next != first) helper = helper.next;
for (int i = 0; i < startNo - 1; i++) {
first = first.next;
helper = helper.next;
}
/* ↓ 如果 startNo = 1, 下面这种方法就不对了 ↓
for (int i = 0; i < startNo - 2; i++)
helper = helper.next;
// 移动 startNo - 2 + 1 次
first = helper.next;
*/
// 2. 开始数数, 让结点逐个出圈
while (helper != first) { // 说明圈里只有 1 个结点了
// 2.1 让 first, helper 同时移动 countNum - 1 次
for (int i = 0; i < countNum - 1; i++) {
first = first.next;
helper = helper.next;
}
// 此时, first 指向的结点即为要出圈的结点
System.out.println("出圈! " + first);
first = first.next;
helper.next = first;
// 出圈结点 此时因没有被任何引用所引用, 而被垃圾回收
}
System.out.println("last Node: " + first);
}
// 遍历环形链表
public void showList() {
if (first == null) {
System.out.println("链表为空");
return;
}
Boy curBoy = first;
do {
System.out.println(curBoy);
curBoy = curBoy.next;
} while (curBoy != first);
}
}
class Boy {
public int no;
public Boy next;
public Boy(int no) {
super();
this.no = no;
}
@Override
public String toString() {
return "Boy [no=" + no + "]";
}
}