单向环形链表--约瑟夫问题
首先来看一个著名的约瑟夫（Josephu）问题
设编号为1，2，3...，n个人围坐一圈，约定编号为k(1<=k <= n)的人从1开始报数，数到m的那个人出列，紧接着他的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止，由此产出一个编号的序列
如何解决上述问题？
这里就可以使用单向环形链表
大概思路如下
先创建一个有n个节点的环形单向环形链表，然后由k节点开始从1开始计数，当记到 m时，对应的节点从链表中删除（出列），然后再从被删除节点的下一个节点开始又从1开始计数，直到最后一个节点从链表中删除。
最后可以得到一个出列的编号序列。
图示 设 n = 5 即有5节点 设 k = 1 即从第一个节点开始计数 设 m = 2 即计数到m的那个节点出列，并记录其编号。
初始节点有5个
当从1号节点开始计数，记到2号节点，此时 m = 2 ,即2号节点出列
此时得到出列的编号序列即 2-> 2号出列，紧接着从3号节点开始从1计数，当记到 4号节点 此时m=2，即4号节点出列
此时得到出列的编号序列即 2->4 4号出列，紧接着从5号节点开始从1计数，当记到1号节点 此时m=2，即1号节点出列
此时得到出列的编号序列即 2->4->1 1号出列，紧接着从3号节点开始从1计数，当记到5号节点 此时m=2，即5号节点出列
当5号节点出列后，环形链表中只有一个节点，因此得到最终的出列顺序为
2->4->1->5->3
进行了我们用代码实现
首先我们得创建一个单向环形链表
创建单向环形链表
思路分析
先创建第一个节点，此时设置一个first指针，并使其指向第一个节点（标识头），在使第一个节点的next域指向自己，从而形成一个最简单的环形链表。
当向这个环形链表中添加一个新节点时
1.设置一个辅助指针curBoy，第一次指向第一个节点
2.使第一个节点（这里就是curBoy）的next域指向新添加进来的节点
3.在设置一个辅助指针Boy,指向新添加进来的节点，并使Boy的next域指向first
4.将curBoy节点后移一位
每次添加节点重复上述操作即完成一个环形链表的创建第一次添加
第n次添加
代码实现创建单向环形链表
创建节点类
class Boy{
private int no; //编号
private Boy next;
public Boy(int no){
this.no = no;
}
public int getNo() {
return no;
}
public Boy getNext() {
return next;
}
public void setNo(int no) {
this.no = no;
}
public void setNext(Boy next) {
this.next = next;
}
}实现单向环形链表
//单向环形链表实现
class CircleSingleLinkdList {
public Boy first = null;//标识链表头
//向环形链表添加指定个数节点
public void addBody(int nums){
if(nums < 1){
System.out.println("环形链表至少需要一个节点");
return;
}
Boy curBoy = null; //辅助指针，用于构建环形链表
for(int i = 1; i <= nums; i ++){
Boy boy = new Boy(i);
//设置第一个节点
if( i == 1){
first = boy;
first.setNext(first); //第一个节点next域指向自己，构成环形链表
curBoy = first;
}
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy; //后移 curBoy
}
}
//显示环形链表中的节点数
public void showBoys(){
if(first == null){
System.out.println("环形链表上没有节点");
return;
}
Boy temp = first;
while(true){
System.out.printf("节点的编号为%d\n",temp.getNo());
if(temp.getNext() == first){
break;//遍历到最后
}
temp = temp.getNext();
}
}
}至此我们已经创建好了一个单向环形链表，接下来我们完成约瑟夫问题
约瑟夫问题
假设环形链表上有5个节点
设 k = 1 即从第一个节点开始计数 设 m = 2 即计数到m的那个节点出列，并记录其编号。
分析
这里涉及到一个问题，当我们出圈的时候，怎么把某个节点移除环形链表呢？ 1.这里需要一个辅助指针helper，默认指向环形链表中的最后一个节点。
当计数前，我们使first和helper移动 k-1次
2.接下来我们开始计数，这里k=1，即从第一个人开始报数，数m下
3.当报数的时候我们将helper和first 前移 m - 1次
4.将first指向的节点从链表中移除
4.1 使first向前移动一位 即 first = first.next
4.2 使 helper.next=first
此时2号节点就从链表中移除。依次类推直到链表中只剩下最后一个节点
代码实现
/**
* 计数元素出圈的编号
* @param k
* @param m
* @param nums
*/
public void countBoy(int k,int m,int nums){
if(first == null || k < 1 || k > nums){
System.out.println("数据非法");
return;
}
//创建辅助指针帮助节点出圈
Boy helper = first;
//使 helper 指向链表中的最后一个节点
while (true){
if(helper.getNext() == first){
break;
}
helper = helper.getNext();
}
//在报数前，先让first和helper移动 k - 1 次
for(int j = 0 ;j < k - 1 ; j++){
first = first.getNext();
helper = helper.getNext();
}
//当报数时，让 first和helper指针同时移动 m - 1 次，然后出圈
while(true){
//圈中只有一个节点
if(helper == first){
break;
}
//first和helper指针同时移动 m - 1 次
for(int j = 0 ;j < m - 1 ; j++){
first = first.getNext();
helper = helper.getNext();
}
//此时first指向的节点，就是要出圈的节点
System.out.printf("节点%d出圈\n",first.getNo());
//将first指向的节点出圈
first = first.getNext();
helper.setNext(first);
}
//当退出while循环时，链表中只有一个节点了
System.out.printf("最后一个节点%d出圈\n",first.getNo());
} CircleSingleLinkdList circleSingleLinkdList = new CircleSingleLinkdList();
circleSingleLinkdList.addBody(5);
circleSingleLinkdList.countBoy(1,2,5);
//
节点2出圈
节点4出圈
节点1出圈
节点5出圈
最后一个节点3出圈腾讯云开发者
