（五）Java数据结构之循环链表解决约瑟夫(Josephus)环问题

桃扇骨 2022-12-13 01:44 166阅读 0赞

![20201009141258375.png][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1bmxvbmc_size_16_color_FFFFFF_t_70][]

package top.baikunlong.linkedlist;
    
    /**
     * @author baikunlong
     * @date 2020/10/9 13:22
     */
    public class Josephus {
        public static void main(String[] args) {
            CircleSingleLinkedList list = new CircleSingleLinkedList();
            list.countBoy(5,1,2);//2 4 1 5 3
            System.out.println();
            list.countBoy(5,2,3);//4 2 1 3 5
        }
    }
    
    /**
     * 循环单链表
     */
    class CircleSingleLinkedList{
        private Boy first;
        public void addBoy(int count){
            if(count<1){
                System.out.println("最小1");
                return;
            }
            Boy temp=null;
            for (int i = 1; i <= count; i++) {
                Boy boy = new Boy(i, "boy" + i);
                if(i==1){//如果是第一个，则赋值给first，让它初始化
                    first = boy;
                    first.next=first;//形成环
                    temp=first;//临时变量，用于移动指针进行添加
                }else {
                    temp.next= boy;//下一个指向最新的boy
                    boy.next=first;//最新的boy的下一个指向first形成环
                    temp=boy;
                }
            }
        }
        public void show(){
            if(first==null){
                System.out.println("空链表");
                return;
            }
            Boy temp=first;
            while(true){
                System.out.println(temp.toString());
                temp=temp.next;
                if(temp==first)return;
            }
        }
    
        /**
         * 报数
         * @param n 总共几个人
         * @param k 从第几个开始报数
         * @param m 数几下
         */
        public void countBoy(int n,int k,int m){
            if(k>n||k<1||m<1){
                System.out.println("数据错误");
                return;
            }
            //重新初始化链表
            addBoy(n);
    
            //因为是单链表，所以首先需要一个临时指针指向first的前一个，帮助出圈
            Boy temp=first;
            while (true){
                if(temp.next==first){
                    break;
                }else {
                    temp=temp.next;
                }
            }
    
            //从第几个开始报数，需要移动指针到开始位置
            for (int i = 0; i < k-1; i++) {
                first=first.next;
                temp=temp.next;
            }
    
            //开始报数
            while (temp!=first){
                //移动m-1次，从1开始数的
                for (int i = 0; i < m - 1; i++) {
                    first=first.next;
                    temp=temp.next;
                }
                //删除
                System.out.println("出圈="+first.toString());
                first=first.next;
                temp.next=first;
            }
            System.out.println("最后的boy="+first.toString());
        }
    }
    class Boy{
        public int no;
        public String name;
        public Boy next;
    
        public Boy(int no,String name) {
            this.no = no;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "Boy{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

[20201009141258375.png]: https://img-blog.csdnimg.cn/20201009141258375.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWt1bmxvbmc_size_16_color_FFFFFF_t_70]: /images/20221123/02f69e45b8d043c19900de9ef1b71271.png