单向环形链表

浅浅的花香味﹌ 2022-11-05 13:57 238阅读 0赞

一：单向环形链表的结构

*  单向环形链表中的节点包含数据域和next指针域，而且最后一个节点的next指针域指向头节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

二：单向环形链表的使用场景

*  约瑟夫问题的解决

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

*  解决思路：

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

*  约瑟夫创建环形链表和遍历思路图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][]

约瑟夫问题-小孩出圈分析图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2][]

约瑟夫代码实现：

Boy实体类

package com.circlelinklist;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 22:16
     */
    public class Boy {
    
        private int no;
    
        private Boy next;
    
        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;
        }
    }

CircleSingleLinkList实体类

package com.circlelinklist;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 22:17
     */
    public class CircleSingleLinkList {
    
        private Boy first = null;
    
        /**
         * 添加构建成环
         * @param num
         */
        public void add(int num) {
    
            if (num < 1) {
                System.out.println("输入的数据不对");
                return;
            }
    
            Boy curBoy = null;
            for (int i = 1; i <= num; 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 list() {
            if (first == null) {
                System.out.println("没有任何小孩");
                return;
            }
    
            Boy curBoy = first;
    
            while (true) {
                System.out.println("当前的小孩为：" + curBoy.getNo());
                if (curBoy.getNext() == first) {
                    break;
                }
                curBoy = curBoy.getNext();
            }
        }
    
        /**
         * 小孩出圈
         * @param startNo
         * @param countNum
         * @param num
         */
        public void outList(int startNo, int countNum, int num) {
            if (first == null || startNo < 1 || startNo > num) {
                System.out.println("输入的参数有误");
            }
    
            Boy helpBoy = first;
            while (true) {
                if (helpBoy.getNext() == first) {
                    break;
                }
                helpBoy = helpBoy.getNext();
            }
    
            for (int i = 0; i < startNo-1; i++) {
                first = first.getNext();
                helpBoy = helpBoy.getNext();
            }
    
            while (true) {
    
                if (first == helpBoy) {
                    break;
                }
    
                for (int i = 0; i < countNum-1; i++) {
                    first = first.getNext();
                    helpBoy = helpBoy.getNext();
                }
    
                System.out.println("出圈的小孩为"+ first.getNo());
    
                first = first.getNext();
                helpBoy.setNext(first);
    
            }
    
            System.out.println("最后出圈的小孩为" + first.getNo());
        }
    }

CircleSingleLinkListDemo实体类

package com.circlelinklist;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 22:18
     */
    public class CircleSingleLinkListDemo {
    
        public static void main(String[] args) {
            CircleSingleLinkList circleSingleLinkList = new CircleSingleLinkList();
            circleSingleLinkList.add(8);
            circleSingleLinkList.list();
            circleSingleLinkList.outList(2, 3, 8);
        }
    }

测试结果：

当前的小孩为：1
    当前的小孩为：2
    当前的小孩为：3
    当前的小孩为：4
    当前的小孩为：5
    当前的小孩为：6
    当前的小孩为：7
    当前的小孩为：8
    出圈的小孩为4
    出圈的小孩为7
    出圈的小孩为2
    出圈的小孩为6
    出圈的小孩为3
    出圈的小孩为1
    出圈的小孩为5
    最后出圈的小孩为8
    
    Process finished with exit code 0

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/5de7d83754434c1cbb2afec781e1a082.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: /images/20221023/3a71ba9f885242cfaa20c137fe21c7a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2]: /images/20221023/c730e9d42a3c491da354049eaff61ba0.png