Java环形链表实现约瑟夫环问题

快来打我* 2024-04-08 13:13 87阅读 0赞

#### 约瑟夫环问题 ####

*  简介
 *  环形链表图解
 *  思路分析
 *   *  图解：
     *   *  1.报数分析
         *  2.指针移动，first指针移动到出圈节点上
         *  3.节点出圈，然后下一次报数从出圈节点的下一个节点开始，就是first节点要后移
 *  代码实现
 *  总结

## 简介 ##

> 约瑟夫问题是个有名的问题：  
> N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

## 环形链表图解 ##

![在这里插入图片描述][fa153e4a0f1641298d447ec2542078c7.png]

## 思路分析 ##

这里我们使用环形链表来实现，这里我用最简单的例子来分析：

*  首先我们需要一个环形链表，我们也不用太多5个节点就行，但是要首尾相连
 *  同时我们需要两个指针节点，来控制报数时的移动，就比如说从第一个人开始，报2次，就相当于 第一个节点报算一次，然后第二个节点报就算第二次，那么第二个节点就被kill了

### 图解： ###

#### 1.报数分析 ####

![在这里插入图片描述][562624e67677485aa274fd36996348a8.png]

#### 2.指针移动，first指针移动到出圈节点上 ####

![在这里插入图片描述][316a1c887eeb4138a124b49583de0149.png]

#### 3.节点出圈，然后下一次报数从出圈节点的下一个节点开始，就是first节点要后移 ####

![在这里插入图片描述][d0399380a46f4b51a0556306c9b97934.png]  
后面也是依此类推

## 代码实现 ##

/**
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/8/28
     */
    public class Josepfu {
        
        public static void main(String[] args) {
        
            CircleList circleList = new CircleList();
            circleList.addNode(new AttenderNode(1));
            circleList.addNode(new AttenderNode(2));
            circleList.addNode(new AttenderNode(3));
            circleList.addNode(new AttenderNode(4));
            circleList.addNode(new AttenderNode(5));
            circleList.countNode(1,2);
        }
    }
    
    /** 环形链表 */
    class CircleList{
        
        /** 定义头节点 */
        private final AttenderNode head = new AttenderNode(-1);
    
        /** 定义一个遍历节点，方便遍历 */
        AttenderNode temp;
    
        /** 给环形链表添加数据 */
        public void addNode(AttenderNode node){
        
            // 环形链表为空时，直接添加
            if (head.next == null){
        
                head.next = node;
                return;
            }
    
            temp = head.next;
            // 只有一个节点时
            while(temp.next == null){
        
                temp.next = node;
                node.next = head.next;
                return;
            }
    
            // 只有当节点的next指向head.next时，循环结束
            while (temp.next != head.next){
        
                temp = temp.next;
            }
            // 将节点插入到最后一个节点
            temp.next = node;
            // 并将他的next指向头节点
            node.next = head.next;
        }
    
        /** 打印环形链表 */
        public void showNode(){
        
            temp = head.next;
            // 只要节点的下一个节点不是头节点就继续打印
            while (temp.next != head.next){
        
                System.out.println(temp);
                temp = temp.next;
            }
            // 打印最后一个节点
            System.out.println(temp);
        }
    
        /** 计算环形链表中有多少个节点 */
        public int getLength(){
        
            int count = 0;
            temp = head.next;
            while (temp.next != head.next){
        
                count++;
                temp = temp.next;
            }
            count++;
            return count;
        }
    
        /**
         * 约瑟夫环的实现方法
         * @param startNode 从哪个节点开始
         * @param count 第几个出圈
         */
        public void countNode(int startNode,int count){
        
            // 定义一个头节点
            AttenderNode first = head.next;
            temp = head.next;
            // 将temp指向头节点的前一个节点
            while (true){
        
                if (temp.next == head.next){
        
                    break;
                }
                temp = temp.next;
            }
    
            // 根据startNode，改变从哪个节点开始
            for (int i = 0; i < startNode - 1 ; i++) {
        
                first = first.next;
                temp = temp.next;
            }
    
            // 出圈
            while (true){
        
                // 结束
                if (temp == first){
        
                    break;
                }
                // 根据count移动
                for (int i = 0; i < count - 1; i++) {
        
                    first = first.next;
                    temp = temp.next;
                }
                // 这时，这个first节点就是出圈的
                System.out.println(first);
                // 后移，同时让前一个节点指向first
                first = first.next;
                temp.next = first;
    
            }
            System.out.println("存活的节点"+temp);
    
        }
    }
    
    /** 定义节点 */
    class AttenderNode {
        
        int id;
        AttenderNode next;
    
        @Override
        public String toString() {
        
            return "AttenderNode{" +
                    "id=" + id +
                    '}';
        }
    
        public AttenderNode(int id) {
        
            this.id = id;
        }
    }

打印结果：

AttenderNode{
        id=2}
    AttenderNode{
        id=4}
    AttenderNode{
        id=1}
    AttenderNode{
        id=5}
    存活的节点AttenderNode{
        id=3}

## 总结 ##

博主也是学习者，不一定是对的，有什么问题可以评论，发现错误，共同学习，谢谢大家看到最后!

[fa153e4a0f1641298d447ec2542078c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/f8fc3b8835ff4b22adbe0faea597dead.png
[562624e67677485aa274fd36996348a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/734af163105c45649b56c1d9a4001a1a.png
[316a1c887eeb4138a124b49583de0149.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0183487c93594d66a208730bd78cb1ba.png
[d0399380a46f4b51a0556306c9b97934.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/25a6eeb3f65242159a12b977790013a2.png