个人简介

前言

单向环形链表应用场景

1.josepfu(约瑟夫)问题

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

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束 当m=2时，从1开始，如图 出圈的顺序:2->4->1->5->3

2.构建一个单向的环形链表思路

1. 先创建第一个节点, 让 first 指向该节点，并形成环形，first.next=first;
2. 后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可. 例如:curBoy 指针指向当前最先加入的结点 newBoy指向即将加入(添加节点)的节点 first指针指向第一个节点 curBoy.next = newBoy newBot.next = first curBoy = newBoy; 如图：

遍历环形链表

1. 先让一个辅助指针(变量) curBoy，指向first节点
2. 然后通过一个while循环遍历 该环形链表即可 curBoy.next == first 结束

3.代码实现定义环形链表

实现添加与遍历

4.解决约瑟夫问题

孩子出圈的思路分析与代码实现 根据用户的输入，生成一个小孩出圈的顺序 n = 5 , 即有5个人 k = 1, 从第一个人开始报数 m = 2, 数2下

1. 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点. 补充： 小孩报数前，先让 first 和 helper 移动 k - 1次 //定义好从第几个小孩开始
2. 当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次
3. 这时就可以将first 指向的小孩节点 出圈 first = first .next helper.next = first 原来first 指向的节点就没有任何引用，就会被回收

如图出圈的顺序 2->4->1->5->3 初始化: 模拟第一个数出列 first = first .next helper.next = first 数据2没有节点指向，将会被回收

代码如下：

/**
     * @Author: 灰爪哇
     * @Description:  小孩出圈的实例
     * @Date: 2022/12/31 17:26
     * @Parms: [startNo为从第几个小孩开始计数, CountNum为计多少次数, nums为小孩的总数]
     * @ReturnType: void
     */
    public void countBoy(int startNo,int CountNum,int nums){
          
   
        //定义一个helper制定，指向最后节点
        if (first == null||startNo < 1||startNo >nums){
          
   
            System.out.println("参数输入有误");
            return;
        }
        Boy helper =first;
        while (true){
          
   
            if (helper.next == first){
          
   
                break;
            }
            helper = helper.next;
        }
        //根据startNo，first和helper同时移动startNo -1步
        for (int i = 0; i < startNo -1; i++) {
          
   
            first =first.next;
            helper=helper.next;
        }
        //根据countNums，开始遍历报数，first和helper同时移动CountNum -1步，走完后，first所指的小孩出圈 ==》》helper.next = first.next
        //当helper = first 侧退出循坏
        while (true){
          
   
            if (helper == first){
          
   
                System.out.println("这是最后出圈的小孩"+helper.no);
                break;
            }
            for (int i = 0; i < CountNum -1; i++) {
          
   
                first =first.next;
                helper=helper.next;
            }
            System.out.println("第"+first.no+"个小孩出圈");
            first = first.next;
            helper.next = first;
        }
    }
}

5.总体代码

总结