【Java数据结构和算法】007-链表：循环链表和约瑟夫问题

訾博ZiBo

发布于 2025-01-06 16:34:53

7800

代码可运行

文章被收录于专栏：全栈开发工程师全栈开发工程师

运行总次数：0

代码可运行

0、警醒自己

1、学习不用心，骗人又骗己；

2、学习不刻苦，纸上画老虎；

3、学习不惜时，终得人耻笑；

4、学习不复习，不如不学习；

5、学习不休息，毁眼伤身体；

7、狗才等着别人喂，狼都是自己寻找食物；

一、循环列表和约瑟夫问题

1、单向环形列表应用场景

Josephu(约瑟夫、约瑟夫环) 问题：

Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列；

提示：用一个不带头结点（可以带也可以不带）的循环链表来处理Josephu问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除，算法结束；

2、单向环形链表介绍

（第一个节点指定第二个节点、第二个节点指向第三个节点……最后一个节点又指向第一个节点，由此形成了一个环）

3、约瑟夫问题解决思路图解

二、添加节点

（瑕疵方案-自己想的，添加节点的方法是跟老师讲的一样的，遍历写得不一样，我写的有瑕疵，老师写的会在“代码演示”下面贴出来）

1、实现逻辑图解

2、代码演示

我写的：

package com.zb.ds;

public class TestJosephu {
    public static void main(String[] args) {
        CircularList list = new CircularList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.show();
    }
}
//list
class CircularList{
    BoyNode first;
    BoyNode current;

    //添加一个节点
    public void add(int id){
        //这里主要目的是演示添加节点，不再考虑id重复的情况
        BoyNode boy = new BoyNode(id);
        //如果first为null，说明这是第一个节点
        if(first==null){
            first = boy;
            current = boy;
            current.next = boy;
        }else {
            current.next = boy;
            current = boy;
            current.next = first;
        }
    }

    //循环遍历输出boy，我们从first输出到current
    public void show(){
        if(first==null){
            System.out.println("无任何节点！");
            return;
        }
        BoyNode temp = first;
        System.out.println(temp.id);
        do {
            temp = temp.next;
            System.out.println(temp.id);
        }while (temp.next!=first);
    }
}
//boy
class BoyNode{

    int id;
    BoyNode next;

    public BoyNode(int id) {
        this.id = id;
    }
}

根据老师讲解写的（遍历）：

package com.zb.ds;

public class TestJosephu {
    public static void main(String[] args) {
        CircularList list = new CircularList();
        list.add(5);
        list.show();
    }
}
//list
class CircularList{
    //创建一个first节点，没有编号
    BoyNode first;
    //创建curBoy，辅助我们构建环形列表，主要作用是记录环形列表的尾
    BoyNode curBoy;

    //添加节点，构建环形列表，nums为节点的数量
    public void add(int nums){
        //验证nums，如果nums<1，则返回
        if(nums<1){
            System.out.println("nums不能小于1");
            return;
        }
        //使用for循环创建环形列表
        for (int i = 1; i <= nums; i++) {
            //根据编号创建节点
            BoyNode boy = new BoyNode(i);
            //如果是第一个小孩，咱们对齐进行记录
            if(i==1){
                first = boy;
                //自己成环
                first.next = first;
                curBoy = first;
            }else {
                curBoy.next = boy;
                boy.next = first;
                curBoy = boy;
            }
        }
    }

    //循环遍历输出boy，我们从first输出到current
    public void show(){
        System.out.println("当前链表的所有小朋友编号：");
        if(first==null){
            System.out.println("无任何节点！");
            return;
        }
        BoyNode temp = first;
        while (true){
            System.out.print(temp.id + " ");
            if(temp.next==first){
                //此时当前节点的next指向first，说明是最后一个节点
                break;
            }
            temp = temp.next;
        }
        System.out.println();
    }
}
//boy
class BoyNode{

    int id;
    BoyNode next;

    public BoyNode(int id) {
        this.id = id;
    }
}

3、运行结果

我写的：

根据老师讲解写的：

评析：

区别不大！

三、出圈（瑕疵方案-自己想的）

1、实现逻辑图解

2、代码演示

（再次明确我们的需求：有n个小朋友、从第k个小朋友开始数，数到m的出场！）

package com.zb.ds;

public class TestJosephu {
    public static void main(String[] args) {
        CircularList.go(10,3,6);
    }
}
//list
class CircularList{
    BoyNode first;
    BoyNode current;

    //添加一个节点
    public void add(int id){
        //这里主要目的是演示添加节点，不再考虑id重复的情况
        BoyNode boy = new BoyNode(id);
        //如果first为null，说明这是第一个节点
        if(first==null){
            first = boy;
            current = boy;
            current.next = boy;
        }else {
            current.next = boy;
            current = boy;
            current.next = first;
        }
    }

    //循环遍历输出boy，我们从first输出到current
    public void show(){
        System.out.println("当前链表的所有小朋友编号：");
        if(first==null){
            System.out.println("无任何节点！");
            return;
        }
        BoyNode temp = first;
        System.out.print(temp.id);
        do {
            temp = temp.next;
            if(temp.id!=temp.next.id){
                System.out.print(temp.id);
            }
        }while (temp.next!=first);
        System.out.println();
    }

    //进行出场模拟：有n个小朋友、从第k个小朋友开始数，数到m的出场
    //这里之演示简化之后的模型，不考虑过多其他情况
    public static void go(int n,int k,int m){
        //初始化list
        CircularList list = new CircularList();
        //初始化n个小朋友
        for (int i = 1; i <= n; i++) {
            list.add(i);
            System.out.println("初始化了第" + i + "个小朋友！");
        }

        //定义一些辅助变量
        BoyNode last = new BoyNode(-1),next = new BoyNode(-2);
        int num = 0;
        BoyNode temp = list.getFirst();
        boolean add = false;
        while (last!=next){
            //数之前记录上一个节点
            last = temp;
            if(temp.id==k){
                add = true;
            }
            if(add){
                //数数
                num++;
            }
            temp = temp.next;
            //数之后记录下一个节点
            next = temp.next;
            if(num==m){
                //如果first出圈了，就像下一个赋值给first
                if(temp.id==list.first.id){
                    list.first=next;
                }
                System.out.println("出圈小朋友的id为：" + temp.id);
                //数到了，直接将
                last.next = next;
                k = next.id;
                num=0;
                //显示当前剩余节点
                list.show();
            }
        }
        //跳出循环之后，还有两个，分别出局即可
        System.out.println("出圈小朋友的id为：" + temp.id);
        last.next = last;
        //显示当前剩余节点
        list.show();
        System.out.println("出圈小朋友的id为：" + list.first.id);
        list.first = null;
        list.show();
    }

    public BoyNode getFirst() {
        return first;
    }

    public BoyNode getCurrent() {
        return current;
    }
}
//boy
class BoyNode{

    int id;
    BoyNode next;

    public BoyNode(int id) {
        this.id = id;
    }
}

3、运行结果

（看上去，我们成功了，实际上还是存在瑕疵的！）

初始化了第1个小朋友！
初始化了第2个小朋友！
初始化了第3个小朋友！
初始化了第4个小朋友！
初始化了第5个小朋友！
初始化了第6个小朋友！
初始化了第7个小朋友！
初始化了第8个小朋友！
初始化了第9个小朋友！
初始化了第10个小朋友！
出圈小朋友的id为：9
当前链表的所有小朋友编号：
1234567810
出圈小朋友的id为：5
当前链表的所有小朋友编号：
123467810
出圈小朋友的id为：2
当前链表的所有小朋友编号：
13467810
出圈小朋友的id为：10
当前链表的所有小朋友编号：
134678
出圈小朋友的id为：8
当前链表的所有小朋友编号：
13467
出圈小朋友的id为：1
当前链表的所有小朋友编号：
3467
出圈小朋友的id为：4
当前链表的所有小朋友编号：
367
出圈小朋友的id为：3
当前链表的所有小朋友编号：
67
出圈小朋友的id为：7
当前链表的所有小朋友编号：
6
出圈小朋友的id为：6
当前链表的所有小朋友编号：
无任何节点！

四、出圈（较完美方案-老师讲的）

1、思路分析

2、代码演示

package com.zb.ds;

public class TestJosephu {
    public static void main(String[] args) {
        CircularList list = new CircularList();
        list.go(5,1,2);
    }
}
//list
class CircularList{
    //创建一个first节点，没有编号
    BoyNode first;
    //创建curBoy，辅助我们构建环形列表，主要作用是记录环形列表的尾
    BoyNode curBoy;

    //添加节点，构建环形列表，nums为节点的数量
    public void add(int nums){
        //验证nums，如果nums<1，则返回
        if(nums<1){
            System.out.println("nums不能小于1");
            return;
        }
        //使用for循环创建环形列表
        for (int i = 1; i <= nums; i++) {
            //根据编号创建节点
            BoyNode boy = new BoyNode(i);
            //如果是第一个小孩，咱们对齐进行记录
            if(i==1){
                first = boy;
                //自己成环
                first.next = first;
                curBoy = first;
            }else {
                curBoy.next = boy;
                boy.next = first;
                curBoy = boy;
            }
        }
    }

    //循环遍历输出boy，我们从first输出到current
    public void show(){
        System.out.println("当前链表的所有小朋友编号：");
        if(first==null){
            System.out.println("无任何节点！");
            return;
        }
        BoyNode temp = first;
        while (true){
            System.out.print(temp.id + " ");
            if(temp.next==first){
                //此时当前节点的next指向first，说明是最后一个节点
                break;
            }
            temp = temp.next;
        }
        System.out.println();
    }
    /**
     * 进行出场模拟：有n个小朋友、从第k个小朋友开始数，数到m的出场
     * 这里之演示简化之后的模型，不考虑过多其他情况
     * @param n 有几个小孩
     * @param k 从第几个小孩开始数
     * @param m 数几次出圈
     */
    public void go(int n,int k,int m){
        //首先进行数据校验
        if(k<1 || k>n){
            System.out.println("参数输入有误，请重新输入！");
            return;
        }
        //1、创建一个辅助变量helper，事先应该指向环形列表的最后一个节点；
        //创建环形链表
        add(n);
        //创建辅助变量helper，将helper指向环形链表的最后一个节点
        //其实这个时候最后一个节点就是curBoy，我写的curBoy是全局变量，老师写的是局部变量
        //写法一：老师写的
        BoyNode helper = first;
        //此时说明helper是最后一个节点了
        while (helper.next != first) {
            helper = helper.next;
        }
        //写法二：因为咱用的是全局变量，所有在add的时候curBoy指向的就是最后一个节点，所以直接赋值即可
        System.out.println(helper.id == curBoy.id);//咱在这里做一个的简单的验证，实际使用的时候可以直接赋值
        //2、小孩报数前，让first和helper同时移动移动k-1个位置；
        for (int i = 0; i < k-1; i++) {
            first = first.next;
            helper = helper.next;
        }
        //3、当小孩报数时，让first和helper同时移动m-1个位置；
        //此时说明圈中只有一个节点
        while (first != helper) {
            //让first和helper同时移动m-1个位置
            for (int i = 0; i < m - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
            //移动完了，此时将first指向的小孩出圈
            System.out.println("出圈：" + first.id);
            first = first.next;
            helper.next = first;
        }
        //退出while循环的时候，剩下最后一个节点
        System.out.println("出圈：" + first.id);
    }
}
//boy
class BoyNode{

    int id;
    BoyNode next;

    public BoyNode(int id) {
        this.id = id;
    }
}

3、运行结果

五、总结

当理解老师的大致思路之后，觉得自己可以代码实现，最终发现自己写的代码有一些不完美，而且容易扰乱思路。但这是非常有必要的，因为如果全部跟着老师的思路来，确实不会出任何问题，但自己的思考在哪里呢？狗才等着别人喂，狼都是自己寻找食物；我希望自己能够在学习老师讲解的基础上有自己的想法或者理解。需要注意的一点是，老师的解题方法是比较完善的，自己的写法往往考虑不到一些情况，这里是要重视老师对各种情况的把控，毕竟理想状态是很少的，实际工作中不是理想状态！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-06，如有侵权请联系 cloudcommunity@tencent.com 删除

链表