单向循环链表--解决约瑟夫问题
一、单向循环链表的应用场景
1.1 问题描述
Josephu(约瑟夫、约瑟夫环) 问题 Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由 此产生一个出队编号的序列。 提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结 点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直 到最后一个结点从链表中删除算法结束。
1.2 问题化简
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
n = 5 , 即有5个人 k = 1, 从第一个人开始报数 m = 2, 数2下
出圈的顺序 2->4->1->5->3
二 单向循环链表的实操
2.1 首先节点创建
// 创建一个boy类，表示一个节点
class Boy {
private int no;
private Boy next;// 指向下一个节点，默认为null
public Boy(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
2.2 单向循环链表的添加（构建）
创建环形链表的思路图解
先创建第一个节点, 让 first 指向该节点，并形成环形
后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.
class CircleSingleLinkedList{
//创建一个first节点，当前没有编号
private Boy first = null;
//添加一个小孩节点，构建成为一个环形的链表
public void addBoy(int nums){
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 = first; //让curBoy指向第一个小孩
}else{
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy; //curBoy永远紧跟当前链表中的最新节点
}
}
}
}
2.2 遍历单向循环链表
//遍历当前的环形链表
public void showBoy(){
//判断链表是否为空
if(first ==null ){
System.out.println("没有任何小孩");
return;
}
//因为first不能动，因此我们仍然使用一个辅助指针完成遍历
Boy curBoy = first;
while(true){
System.out.printf("小孩的编号 %d \n", curBoy.getNo());
if(curBoy.getNext() == first){
break;
}
curBoy = curBoy.getNext();
}
}
2.3 小孩出圈问题分析
根据用户的输入，生成一个小孩出圈的顺序 n = 5 , 即有5个人 k = 1, 从第一个人开始报数 m = 2, 数2下
需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点. 补充： 小孩报数前，先让 first 和 helper 移动 k - 1次
当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次
这时就可以将first 指向的小孩节点 出圈 first = first .next helper.next = first 原来first 指向的节点就没有任何引用，就会被回收
出圈的顺序 2->4->1->5->3
代码实现：
// 根据用户的输入，计算出小孩出圈的顺序
/**
*
* @param startNo
* 表示从第几个小孩开始数数
* @param countNum
* 表示数几下
* @param nums
* 表示最初有多少小孩在圈中*/
public void countBoy(int startNo,int countNum,int nums){
if(first == null || startNo<1||startNo>nums){
System.out.println("参数输入有误， 请重新输入");
return;
}
//创建要给辅助指针，帮助完成小孩出圈
Boy helper = first;
//需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
while(true){
if(helper.getNext() == first){ //说明helper指向最后小孩节点
break;
}
helper = helper.getNext();
}
//小孩报数前，先让 first 和 helper 移动 startNo - 1次
for(int j=0;j<startNo-1;j++){
first = first.getNext();
helper = helper.getNext();
}
//当小孩报数时，让first 和 helper 指针同时 的移动 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); //
}
System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());
}
