Java数据结构与算法（三）：链表

Myth丶恋晨 2022-12-08 14:25 183阅读 0赞

## 1. 单链表介绍 ##

链表是有序的列表，但是它在内存中是存储如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center]

*  链表是以节点的方式来存储，是链式存储；
 *  每个节点包含 data 域，next 域（指向下一个节点）；
 *  如上图：链表的各个节点不一定是连续存储；
 *  链表分 带头节点的链表 和没有头节点的链表，根据实际的需求来确定；
    
     *  单链表（带头节点）逻辑结构示意图如下：  
        ![在这里插入图片描述][20200920103136660.png_pic_center]

## 2. 单链表的应用实例 ##

使用带头节点的单项链表实现 水浒英雄排行榜管理 完成对英雄人物的增删改查操作。

*  **第一种方法在添加英雄时，直接添加到链表的尾部：**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 1]
 *  **第二种方式在添加英雄时，根据排名将英雄插入到指定位置（如果已有这个排名，则添加失败，并给出提示）**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 2]
 *  **修改节点信息**

1.  先找到该节点，然后遍历；
2.  temp.name == newHeroNode; temp.nickName == newHeroNode.nickName;

*  **删除节点**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 3]
 *  **代码实现**

package com.lele.linkedlist;
    
    /**
     * author: hwl
     * date: 2020/9/19 16:10
     * version: 1.0.0
     * modified by:
     * description:
     */
    public class SingleLinkedListDemo {
        
    
        public static void main(String[] args) {
        
            // 创建节点
            HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
            HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
            HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
            HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    
            // 创建链表
            SingleLinkedList singleLinkedList = new SingleLinkedList();
            // 不考虑顺序
    //        singleLinkedList.add(hero1);
    //        singleLinkedList.add(hero2);
    //        singleLinkedList.add(hero3);
    //        singleLinkedList.add(hero4);
    //        singleLinkedList.list();
    
            // 按照编号顺序插入
            singleLinkedList.addByOrder(hero1);
            singleLinkedList.addByOrder(hero4);
            singleLinkedList.addByOrder(hero2);
            singleLinkedList.addByOrder(hero3);
            singleLinkedList.addByOrder(hero3);
            singleLinkedList.list();
    
            // 测试修改节点
            HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
            singleLinkedList.update(newHeroNode);
            System.out.println("修改后的链表情况~~");
            singleLinkedList.list();
    
            // 测试查找节点
            System.out.println("测试查找");
            singleLinkedList.query(1);
            System.out.println(singleLinkedList.query(1));
    
    
            // 测试删除节点
            singleLinkedList.del(1);
            singleLinkedList.del(4);
            singleLinkedList.del(2);
            singleLinkedList.del(3);
            System.out.println("删除后的链表情况~~");
            singleLinkedList.list();
        }
    }
    
    // 定义 SingleLinkedList
    class SingleLinkedList {
        
        // 先初始化一个头节点，头节点不要动，不存放具体的数据
        private HeroNode head = new HeroNode(0, "", "");
    
        // 添加节点到单链表中
        // 思路，当不考虑编号顺序时
        // 1. 找到当前链表的最后节点
        // 2. 将最后这个节点的next指向 新的节点
        public void add(HeroNode heroNode) {
        
            // 因为head节点不能动，因此我们需要一个辅助变量 temp
            HeroNode temp = head;
            // 遍历链表，找到最后
            while(true) {
        
                // 找到链表的最后
                if(temp.next == null) {
        
                    break;
                }
                // 如果没有找到最后，将temp后移
                temp = temp.next;
            }
            // 当退出while循环时，temp就指向了链表的最后
            // 将最后这个节点的next指向 新的节点
            temp.next = heroNode;
        }
    
        // 第二种方式在添加英雄时，根据排名蒋英雄插入到指定位置
        // 如果已经存在该排名，则添加失败，并给出提示
        public void addByOrder(HeroNode heroNode) {
        
            // 因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
            // 因为单链表，由于我们找的temp是位于 添加位置的前一个节点，否则不能插入
            HeroNode temp = head;
            boolean flag = false; // flag 标志添加的编号是否存在，默认为false
            while(true) {
        
                if (temp.next == null) {
         // temp已经在链表的最后
                    break;
                }
                if (temp.next.no > heroNode.no) {
         // 位置找到，就在temp的后面插入
                    break;
                } else if (temp.next.no == heroNode.no) {
         // 说明将要添加的heroNode的编号已经存在
                    flag = true; // 标识编号已经存在
                    break;
                }
                temp = temp.next; // 后移，遍历当前链表
            }
            // 判断flag 的值
            if (flag) {
         // 编号已经存在，不能添加
                System.out.printf("准备插入的英雄的编号 %d 已经存在了，不能插入\n", heroNode.no);
            } else {
        
                // 插入到链表中，temp的后面
                heroNode.next = temp.next;
                temp.next = heroNode;
            }
        }
    
        // 查找链表中是否存在某个节点,根据编号查找
        public HeroNode query(int no) {
        
            // 判断是否为空
            if (head.next == null) {
        
                System.out.println("链表为空~");
                return null;
            }
            HeroNode temp = head.next; // 定义一个辅助变量
            while(true) {
        
                if (temp == null) {
        
                    System.out.println("链表没有该节点~~");
                    return null;// 已经遍历完链表
                }
                if (temp.no == no) {
        
                    return temp;
                }
                temp = temp.next;
            }
        }
    
        // 修改节点的信息，根据no编号来修改，即no编号不能改
        // 1. 根据 newHeroNode 的no来修改即可
        public void update(HeroNode newHeroNode) {
        
            // 判断是否为空
            if (head.next == null) {
        
                System.out.println("链表为空~");
                return;
            }
            // 找到需要修改的节点，根据no编号
            // 定义一个辅助变量
            HeroNode temp = head.next;
            boolean flag = false; // 表示是否找到该节点
            while(true) {
        
                if (temp == null) {
        
                    break; // 已经遍历完链表
                }
                if (temp.no == newHeroNode.no) {
         // 找到需要修改的节点
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            // 根据 flag 判断是否找到要修改的节点
            if (flag) {
        
                temp.name = newHeroNode.name;
                temp.nickName = newHeroNode.nickName;
            } else {
         // 没有找到
                System.out.printf("没有找到编号为 %d 的节点，无法修改\n", newHeroNode.no);
            }
        }
    
        // 删除节点
        // 思路
        // 1.head不能动,因为我们需要一个temp辅助节点找到待删除节点的前一个节点
        // 2.说明我们在比较时，是 temp.next.no 和 需要删除的节点的no比较
        public void del (int no) {
        
            HeroNode temp = head;
            boolean flag = false; //标志是否找到待删除节点的
            while(true) {
        
                if (temp.next == null) {
          // 已经到链表的最后
                    break;
                }
                if (temp.next.no == no) {
          // 找到待删除节点的前一个节点
                    flag = true;
                    break;
                }
                temp = temp.next; // temp后移，遍历
            }
            // 判断flag
            if (flag) {
         // 找到
                // 可以删除
                temp.next = temp.next.next;
            } else {
        
                System.out.printf("要删除的 %d 节点不存在\n", no);
            }
        }
    
        // 显示链表（遍历）
        public void list(){
        
            // 判断链表是否为空
            if (head.next == null) {
        
                System.out.println("链表为空");
                return;
            }
            // 因为头节点不能动，因此我们需要一个辅助变量来遍历
            HeroNode temp = head.next;
            while(true) {
        
                // 判断是否到了链表的尾部
                if (temp == null) {
        
                    break;
                }
                // 输出节点的信息
                System.out.println(temp);
                //将temp后移，一定小心
                temp = temp.next;
            }
        }
    }
    
    // 定义HeroNode，每个HeroNode对象就是一个节点
    class HeroNode {
        
        public int no;
        public String name;
        public String nickName;
        public HeroNode next;  // 指向下一个节点
    
        // 构造方法
        public HeroNode(int no, String name, String nickName) {
        
            this.no = no;
            this.name = name;
            this.nickName = nickName;
        }
    
        // 重写toString
        @Override
        public String toString() {
        
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickName='" + nickName + '\'' +
                    '}';
        }
    }

## 3. 单链表面试题 ##

**1. 求单链表中有效节点的个数**

*  代码如下：

/**
    * 方法：获取单链表节点个数（如果带头节点，需求不统计头节点）
     * @param head 链表的头结点
     * @return 链表的有效节点个数
     */
    public static int getLength(HeroNode head) {
        
        if (head.next == null) {
          // 空链表
            return 0;
        }
        int length = 0; // 表示链表的长度
        // 定义一个辅助变量，这里没有统计头节点
        HeroNode cur = head.next;
        while(cur != null) {
        
            length++;
            cur = cur.next; // 遍历
        }
        return length;
    }

**2. 查找单链表中的倒数第k个节点**

*  代码如下：

/**
     * 查找单链表中的倒数第k个节点
     * 思路：
     * 1.编写一个方法，接收head节点，同时接收一个index
     * 2.index表示是倒数第index个节点
     * 3.先把链表从头到尾遍历，得到链表的总长度getLength
     * 4.得到size后，我们从链表的第一个开始遍历（size-index）个，就可以得到
     * 5.如果找到了，则返回该节点，否则返回null
     * @param head
     * @param index
     * @return
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        
        // 如果链表为空，则返回null
        if (head.next == null) {
        
            return null;
        }
        // 第一个遍历 获取链表的长度
        int size = getLength(head);
        // 第二个遍历 size-index,即：倒数的第K个节点
        // 先做一个index 校验
        if (index <= 0 || index > size) {
        
            return null;
        }
        // 定义给辅助变量，for循环定位到倒数的index
        HeroNode cur = head.next;
        for (int i = 0; i < size-index; i++) {
        
            cur = cur.next;
        }
        return cur;
    }
    
    public static int getLength(HeroNode head) {
        
       if (head.next == null) {
          // 空链表
            return 0;
        }
        int length = 0; // 表示链表的长度
        // 定义一个辅助变量，这里没有统计头节点
        HeroNode cur = head.next;
        while(cur != null) {
        
            length++;
            cur = cur.next; // 遍历
        }
        return length;
    }

**3. 单链表的反转**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 5]

*  代码实现

/**
     * 单链表反转
     * @param head 单链表头指针
     */
    public static void reverseList(HeroNode head) {
        
        // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if (head.next == null || head.next.next == null) {
        
            return;
        }
    
        // 定义一个辅助的指针（变量），帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null; // 指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0, "","");
        // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while(cur != null) {
        
            next = cur.next; // 先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next; // 将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur; // 将cur连接到新的链表上
            cur = next; // 让 cur 后移
        }
        // 将 head.next 指向 reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }

**4. 从尾到头打印单链表**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 6]

*  代码实现

/**
     * 单链表的逆序打印
     * 将单链表的各个节点压入栈中，利用栈的先进后出的特点，实现逆序打印的效果
     * @param head 头节点
     */
    public static void reversePrint(HeroNode head) {
        
        if (head.next == null) {
        
            return;  // 空链表，不能打印
        }
        Stack<HeroNode> stack = new Stack<HeroNode>(); // 创建栈
        HeroNode cur = head.next;
        while(cur != null) {
        
            stack.push(cur);  // 入栈
            cur = cur.next; // 后移，继续压入下一个节点
        }
        while(stack.size() > 0) {
        
            System.out.println(stack.pop());  //出栈
        }
    }

## 4 双向链表应用实例 ##

**双向链表的操作分析和实现**  
使用带Head头的双向链表实现 ——水浒英雄排行榜

单向链表的缺点分析：

*  单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
 *  单项链表不能自我删除，需要辅助节点，而双向链表，则可以自我删除；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 7]  
上图说明：  
分析 双向链表的遍历、添加、修改、删除的操作思路及代码实现

*  遍历 和单链表一样，只是可以向前，也可以向后查找；
 *  添加（默认添加到双向链表的最后）
    
     *  先找到双向链表的最后这个节点
     *  temp.next = newHeroNode
     *  newHeroNode.pre = temp;
 *  修改 思路和单链表一样
 *  删除
    
     *  双向链表可以实现自我删除
     *  temp.pre.next = temp.next
     *  temp.next.pre = temp.pre

**代码实现**

package com.lele.linkedlist;
    
    /**
     * author: hwl
     * date: 2020/9/23 6:56
     * version: 1.0.0
     * modified by:
     * description:
     */
    public class DoubleLinkedListDemo {
        
        public static void main(String[] args) {
        
            // 测试
            System.out.println("双向链表的测试");
            //先创建节点
            HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
            HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
            HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
            HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
            // 创建一个双向链表
            DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
            doubleLinkedList.add(hero1);
            doubleLinkedList.add(hero2);
            doubleLinkedList.add(hero3);
            doubleLinkedList.add(hero4);
    
            doubleLinkedList.list();
    
            // 修改
            HeroNode2 heroNode2 = new HeroNode2(4, "公孙胜", "入云龙");
            doubleLinkedList.update(heroNode2);
            System.out.println("修改后的链表情况");
            doubleLinkedList.list();
    
            // 删除
            doubleLinkedList.del(3);
            System.out.println("删除后的链表情况");
            doubleLinkedList.list();
        }
    }
    
    class DoubleLinkedList{
        
        private HeroNode2 head = new HeroNode2(0, "", "");
    
        /**
         *
         * @return 返回头节点
         */
        public HeroNode2 getHead() {
        
            return head;
        }
    
        /**
         * 从双向链表中删除一个节点
         * 说明
         * 1. 对于双向链表，我们可以直接找到要删除的这个节点
         * 2. 找到后，自我删除即可
         * @param no
         */
        public void del (int no) {
        
    
            // 判断当前链表是否为空
            if (head.next == null) {
        
                System.out.println("链表为空，无法删除");
            }
    
            HeroNode2 temp = head.next;  // 辅助变量（指针）
            boolean flag = false; //标志是否找到待删除节点的
            while(true) {
        
                if (temp == null) {
          // 已经到链表的最后
                    break;
                }
                if (temp.no == no) {
          // 找到待删除节点的前一个节点
                    flag = true;
                    break;
                }
                temp = temp.next; // temp后移，遍历
            }
            // 判断flag
            if (flag) {
         // 找到
                // 可以删除
    //            temp.next = temp.next.next;  单项链表的删除方式
                temp.pre.next = temp.next;
                // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针异常
                if(temp.next != null) {
        
                    temp.next.pre = temp.pre;
                }
            } else {
        
                System.out.printf("要删除的 %d 节点不存在\n", no);
            }
        }
    
        /**
         * 修改一个节点的内容，可以看到双向链表的节点内容修改和单链表一样
         * 只是 节点类型改成HeroNode2
         * @param newHeroNode
         */
        public void update(HeroNode2 newHeroNode) {
        
            // 判断是否为空
            if (head.next == null) {
        
                System.out.println("链表为空~");
                return;
            }
            // 找到需要修改的节点，根据no编号
            // 定义一个辅助变量
            HeroNode2 temp = head.next;
            boolean flag = false; // 表示是否找到该节点
            while(true) {
        
                if (temp == null) {
        
                    break; // 已经遍历完链表
                }
                if (temp.no == newHeroNode.no) {
         // 找到需要修改的节点
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            // 根据 flag 判断是否找到要修改的节点
            if (flag) {
        
                temp.name = newHeroNode.name;
                temp.nickName = newHeroNode.nickName;
            } else {
         // 没有找到
                System.out.printf("没有找到编号为 %d 的节点，无法修改\n", newHeroNode.no);
            }
        }
    
        /**
         * 添加一个节点到双向链表的最后
         * @param heroNode
         */
        public void add(HeroNode2 heroNode) {
        
            // 因为head节点不能动，因此我们需要一个辅助变量 temp
            HeroNode2 temp = head;
            // 遍历链表，找到最后
            while(true) {
        
                // 找到链表的最后
                if(temp.next == null) {
        
                    break;
                }
                // 如果没有找到最后，将temp后移
                temp = temp.next;
            }
            // 当退出while循环时，temp就指向了链表的最后
            // 形成一个双向链表
            temp.next = heroNode;
            heroNode.pre = temp;
        }
    
        /**
         * 显示链表（遍历）
         */
        public void list(){
        
            // 判断链表是否为空
            if (head.next == null) {
        
                System.out.println("链表为空");
                return;
            }
            // 因为头节点不能动，因此我们需要一个辅助变量来遍历
            HeroNode2 temp = head.next;
            while(true) {
        
                // 判断是否到了链表的尾部
                if (temp == null) {
        
                    break;
                }
                // 输出节点的信息
                System.out.println(temp);
                //将temp后移，一定小心
                temp = temp.next;
            }
        }
    }
    
    class HeroNode2 {
        
        public int no;
        public String name;
        public String nickName;
        public HeroNode2 next;  // 指向下一个节点
        public HeroNode2 pre; // 指向前一个节点
    
        // 构造方法
        public HeroNode2(int no, String name, String nickName) {
        
            this.no = no;
            this.name = name;
            this.nickName = nickName;
        }
    
        // 重写toString
        @Override
        public String toString() {
        
            return "HeroNode2{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickName='" + nickName + '\'' +
                    '}';
        }
    }

## 5. Josephu 问题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 8]  
Josephu问题：设编号为1,2,3,…n的n个人围坐一圈，约定编号为k（1<=k<n）的人从1开始报数，数到m的那个人出列，她的下一位又从1开始报数，数到m的那个人又出列，依此类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头节点的循环链表来处理Josephu问题，先构成一个有n个节点的单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表删除，然后再从被删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除，算法结束。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 10]  
**代码实现**

package com.lele.linkedlist;
    
    /**
     * author: hwl
     * date: 2020/9/25 7:23
     * version: 1.0.0
     * modified by:
     * description: 约瑟夫问题
     */
    public class Josephu {
        
        public static void main(String[] args) {
        
    
            // 测试构建环形链表及遍历
            CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
            circleSingleLinkedList.addBoy(5); // 添加小孩节点
            circleSingleLinkedList.showBoy();
    
            // 测试 小孩出圈
            circleSingleLinkedList.countBoy(1,2,5); // 2,4,1,5,3
    
        }
    }
    
    // 创建一个环形的单向链表
    class CircleSingleLinkedList {
        
        // 创建一个first节点，当前没有编号
        private Boy first = null;
    
        // 添加小孩节点，构建成一个环形链表
        public void addBoy(int nums) {
        
            // num 做一个数据校验
            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;
                }
            }
        }
    
        // 遍历当前的环形链表
        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();// curBoy 后移
            }
        }
    
        /**
         * 根据用户的输入，计算出小孩出圈的顺序
         * @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 移动 k-1 次
            for (int j = 0; j < startNo - 1; j++) {
        
                first = first.getNext();
                helper = helper.getNext();
            }
            // 当小孩报数时，让 first 和helper 指针同时的移动 m-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());
        }
    }
    
    // 创建一个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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/569fb8f8ffcb48e5b0bb8772945508d7.png
[20200920103136660.png_pic_center]: /images/20221123/058db69f4c7f453284a83025329946e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/312b437314ab4dc791633c0c39362fc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/f08a5587537d45b29e2b70fa5a8a684e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/d2a243a579004a0a8108f43c1ed6e6dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/188eef705f6346299b70efb049c6a194.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/89429e68d1a84649bb25e75fd52fc053.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/91d85190f28a443fb319741316b028e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/d379fdcb8f0e4856a0d9c8415660db07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/4887037b16e24854a128bd88937c2170.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/61b94cae8745414b93e93169d4d00256.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/6ecc86e159a04351b83c619d91aacaae.png