简要：
1 丢手绢问题：这是小时候经常玩的游戏，一群小朋友围到一起，形成一个圈。老师唱歌，小朋友们同时丢手绢，歌曲暂停时，目前拿到手绢的小朋友需要表演一个节目。依次循环下去。
2 而约瑟夫问题与之类似，由一群元素构成的环形链表，首先由某个元素开始报数，报到K时的那个元素需要出圈，然后又由下一个元素开始报数，直到全部的元素出圈时才结束。
编号为1，2……n的n个人围坐一圈，约定编号为k的人开始从1报数，数到n的人出圈，依此类推，会产生一个出圈地编号序列。
这里我们选择用单向循环链表来处理这个问题：
首先我们要创建一个单向循环链表：
1.先创建第一个节点，让first指针指向它，并让它自己形成环状
2.我们在之后每添加一个节点，就加入到环中去
遍历单向循环链表：
1.先定义一个辅助指针，指向first节点；
2.通过while循环遍历即可
思路
1.需要创建一个辅助指针helper,应该让辅助指针只指向链表的最后一个元素
2.再让first和helper移动k-1次到指定位置
3.当小孩报数时，让first和helper同时向前移动m-1次
4.此时，first所指的位置就是要出圈的节点地位置
代码实现
先定义一个类。表示节点的信息
class Boy {
private int no; //每个孩子的编号
Boy next; //指向下一个节点
public Boy(int no){
this.no = no;
}
public void setNext(Boy next) {
this.next = next;
}
public Boy getNext() {
return next;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
再写一个类表示单向循环链表：
1.先写一个添加节点的方法：
我们需要校验输入的nums是否合法，然后根据合理地nums的值，写一个for循环，new Boy类的对象，即节点。接着，我们判断节点的个数，如果是第一个节点，让他自己连接自己，独自成环，如果时多个节点，这个时候就需要辅助指针来帮助我们完成插入操作（这里说一句，由于我们在Boy类中的属性都是private的，所以不能直接通过.next获取下一个节点的位置，而是应该调用getNext()方法，srtNext()同理）
//创建一个first节点
private Boy first = null;
//添加小孩节点，构成环状结构
public void add(int nums){
//先对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 = boy;
}else{ //否则的话，依次往上连接，期间要注意辅助指针的后移
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
2.再写一个打印链表的方法：
从头循环，首先需要判断链表是否为空，为空直接跳出，不为空则继续，让辅助指针帮助我们完成遍历输出的操作。
public void showBoy(){
if(first == null){
return;
}
Boy curBoy = first;
while(true){
System.out.printf("小孩的编号是%d\n",curBoy.getNo());
if(curBoy.getNext() == first){
break;
}
curBoy = curBoy.getNext();
}
}
3.最后就是小孩出圈的操作了
第一步同样是先对传入的数据进行检测，数据合理就让first和helper指针先移动到对应位置上，出圈操作时碰到一个合适的就输出，是一个循环操作，当只剩下一个节点的时候认为遍历结束。
//小孩出圈操作
//startNo表示的是从那个人小孩开始数
//countNum表示的是数几下
//nums表示的是共有几个小孩
public void countBoy(int startNo,int countNum,int nums){
//小对数据进行检验
if(first == null || startNo < 1 || startNo > nums){
System.out.println("参数有误");
return;
}
Boy helper = first;
//要让curBoy指向单向循环链表的最后一个节点
while(true){
if(helper.getNext() == first){
break;
}
helper = helper.getNext();
}
//下一步是报数，在这之前先让两个指针移动到k位置
for(int i = 0;i < startNo - 1;i++){
first = first.getNext();
helper = helper.getNext();
}
//出圈是一个循环操作，直到只剩下一个节点
while(true) {
if (helper == first) {
break;
}
//让helper和first同时移动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); //相当于helper.next = first,由于next是私有的，所以只能这么操作
}
System.out.printf("最后留在圈中的小孩的编号是%d\n",first.getNo());
}
上全部的代码：
package DoubleLinkedListdmeo;
public class Josephu {
public static void main(String[] args) {
CircleLinkedList circleLinkedList = new CircleLinkedList();
circleLinkedList.add(25);
circleLinkedList.showBoy();
//测试小孩出圈是否正确
circleLinkedList.countBoy(6,4,25);
}
}
class CircleLinkedList{
//创建一个first节点
private Boy first = null;
//添加小孩节点，构成环状结构
public void add(int nums){
//先对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 = boy;
}else{ //否则的话，依次往上连接，期间要注意辅助指针的后移
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
public void showBoy(){
if(first == null){
return;
}
Boy curBoy = first;
while(true){
System.out.printf("小孩的编号是%d\n",curBoy.getNo());
if(curBoy.getNext() == first){
break;
}
curBoy = curBoy.getNext();
}
}
//小孩出圈操作
//startNo表示的是从那个人小孩开始数
//countNum表示的是数几下
//nums表示的是共有几个小孩
public void countBoy(int startNo,int countNum,int nums){
//小对数据进行检验
if(first == null || startNo < 1 || startNo > nums){
System.out.println("参数有误");
return;
}
Boy helper = first;
//要让curBoy指向单向循环链表的最后一个节点
while(true){
if(helper.getNext() == first){
break;
}
helper = helper.getNext();
}
//下一步是报数，在这之前先让两个指针移动到k位置
for(int i = 0;i < startNo - 1;i++){
first = first.getNext();
helper = helper.getNext();
}
//出圈是一个循环操作，直到只剩下一个节点
while(true) {
if (helper == first) {
break;
}
//让helper和first同时移动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); //相当于helper.next = first,由于next是私有的，所以只能这么操作
}
System.out.printf("最后留在圈中的小孩的编号是%d\n",first.getNo());
}
}
class Boy {
private int no; //每个孩子的编号
Boy next; //指向下一个节点
public Boy(int no){
this.no = no;
}
public void setNext(Boy next) {
this.next = next;
}
public Boy getNext() {
return next;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
如果还不懂请看b站up主视频讲解：https://www.bilibili.com/video/BV19f4y1Y71p?spm_id_from=333.337.search-card.all.click
本期内容就到这里啦～以上内容均可在 方包博客「http://fang1688.cn」 网站直接搜索名称访问哦。欢迎感兴趣的小伙伴试试，如果本文对您有帮助，也请帮忙点个 赞 + 在看 啦！❤️
欢迎大家加入方包的「优派编程」学习圈子，和多名小伙伴们一起交流学习，向方包 1 对 1 提问、跟着方包做项目、领取大量编程资源等。Q群「891029429」欢迎想一起学习进步的小伙伴~
另外方包最近开发了一款工具类的小程序「方包工具箱」,功能包括：抖音、小红书、快手去水印，天气预报，小说在线免费阅读（内含上万部热门小说），历史今天，生成图片二维码,图片识别文字，ai伪原创文章，数字摇号抽奖,文字转语音MP3功能...
定期分享 it编程干货
⬇️ 点击链接阅读原文直达 方包博客
评论抢沙发