环形单链表解决约瑟夫环问题

红太狼 2022-09-07 14:56 194阅读 0赞

package com.example.datastructrue.linkedlist;
    
    public class JosephuDemo {
        
        public static void main(String[] args) {
        
    
            CircleSingleLinked circleSingleLinked = new CircleSingleLinked();
            System.out.println("参与游戏的人有如下：");
            circleSingleLinked.addBoy(5);
            circleSingleLinked.showBoy();
            System.out.println("出圈顺序如下：");
            circleSingleLinked.boyOut(1,2,5);
        }
    }
    
    class CircleSingleLinked{
        
        private Boy first=null;
    
    //    创建有num个节点的环形单链表
        public void addBoy(int num){
        
            if (num<1){
        
                System.out.println("不能创建0个节点的环形链表");
                return;
            }
            Boy curBoy = null;
            for (int i =1;i<=num;i++){
        
                Boy temp = new Boy(i);
                if(i==1){
        
                    first = temp;
                    first.setNext(first);
                    curBoy = first;
                }
                curBoy.setNext(temp);
                temp.setNext(first);
                curBoy = temp;
            }
        }
    
    //    遍历环形单链表
        public void showBoy(){
        
            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();
            }
        }
    
    //    小孩出圈顺序
        public void boyOut(int startNo,int countNum,int boyNums){
        
            if(startNo<1||startNo>boyNums||countNum<1||first==null){
        
                System.out.println("开始编号不能小于零或大于小孩数量，人数不能少于1");
                return;
            }
            Boy helper = first;
    //        将helper指向第一个节点的后面一个节点，方便下面删除节点
            while (true){
        
                if (helper.getNext()==first){
        
                    break;
                }
                helper = helper.getNext();
            }
    //        将第一个节点移动到开始数数的节点上，并且helper节点在first节点后面
            for (int i = 0;i<startNo-1;i++){
        
                first = first.getNext();
                helper = helper.getNext();
            }
    
            while (true){
        
                if (helper==first){
        
                    System.out.println("最后的幸运儿为："+helper.getNo());
                    break;
                }
                for (int i = 0;i<countNum-1;i++){
        
                    first = first.getNext();
                    helper = helper.getNext();
                }
                System.out.println("编号为"+first.getNo()+"的出圈");
                helper.setNext(first.getNext());
                first = first.getNext();
            }
    
    
    
        }
    }
    
    
    //节点
    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;
        }
    }