单向环形链表

背景

• 数据结构——单向链表

• 博主以b站尚硅谷Java数据结构与算法课进行学习

问题

Josephu（约瑟夫，约瑟夫环）问题

设编号1，2，3…n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它 的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止。

思路

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

  • 先创建第一个节点，让first指向该节点,并形成环形
  • 后面当我们每创建一个新的节点，就把该节点加入到已有的环形链表当中

• 遍历环形链表

  • 先让一个辅助指针（变量）curboy，指向first节点
  • 然后通过一个while循环遍历该环形链表
  • curBoy.next == first遍历结束

• 出圈

  • 先创建一个辅助指针helper，先指向环形链表的最后节点

  • 小孩报数前，先让first和helper移动k-1次

  • 这时就可以将first指向的小孩节点出圈

    • first = first.next

    • helper.next= first

    • 原来的节点没有被引用，就会被回收

步骤

• 创建一个Boy类，表示一个节点

  • 代码实现

    class Boy{
        @SuppressWarnings("all")
        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;
        }
    }

• 创建一个单向环形链表CircleSingleLinkedList类

  • 创建一个first节点，当前没有编号

    • 代码实现

      class CircleSingleLinkedList{
          //创建一个first节点，当前没有编号
          private Boy first = new Boy(-1);
      }

• 添加小孩节点addBoy，构建一个环形链表

  • 代码实现

    public void addBoy(int nums){
        //nums做一个数据校验
        if(nums<1){
            System.out.println("nums不正确");
            return;
        }
        Boy curBoy = null;//辅助变量，帮助构建环形链表
        //使用for来创建我们的环形链表
        for(int i = 1;i<=nums;i++){
            //根据编号，创建小孩节点
           Boy boy = new Boy(i);
           //如果是第一个小孩
            if(i==1){
                first =boy;
                first.setNext(first);//构成环
                curBoy = first;//让curBoy指向第一个小孩
            }else{
                  curBoy.setNext(boy);
                  boy.setNext(first);
                  curBoy = boy;
        }
        }
    }

• 遍历当前环形链表

  • 代码实现

    public void showBoy(){
        //判断链表是否为空
            if(first == null){
                System.out.println("没有任何小孩");
                return;
            }
        //因为first不能动，所以使用辅助指针
        Boy curBoy = first;
            while(true){
                System.out.printf("小孩的编号%d\n",curBoy.getNo());
                if(curBoy.getNext()==first){//说明遍历完毕
                    break;
                }
                curBoy = curBoy.getNext();//curBoy后移
            }
    
    
    }

• 根据用户输入，计算小孩出圈的顺序

  • 代码实现

    //根据用户输入，计算小孩出圈的顺序
     public void countBoy(int startNo,int countNum,int nums){
         //startNo表示从哪个小孩开始数
         //countNum表示数几下
         //nums表示最初有多少小孩在圈中
         if(first==null||startNo<1||startNo>nums){
             System.out.println("参数输入有误，请重新输入");
             return;
         }
         //创建辅助指针，帮助小孩出圈
         Boy helper = first;
         //应指向环形链表最后节点
         while(true){
             if(helper.getNext() == first){
                 //说明helper指向最后小孩节点
                 break;
             }
             helper = helper.getNext();
         }
         //小孩报数前，先让first和helper移动k-1次
         for (int j= 0;j<startNo-1;j++){
             first = first.getNext();
             helper = helper.getNext();
         }
         //当小孩报数时，让first和helper指针同时移动m-1次,直到圈中只有一个人
         while(true){
             if(helper == first){//说明圈中只有一个人
             break;
             }
             //让first和helper指针同时移动countNum-1，然后出圈
             for(int j= 0;j<countNum-1;j++){
                 first = first.getNext();
                 helper = helper.getNext();
             }
             //这时first指向的节点就是小孩出圈的节点
             System.out.printf("小孩%d出圈\n",first.getNo());
             //这时将first指向小孩节点出圈
             first = first.getNext();
             helper.setNext(first);
         }
         System.out.printf("最后留在圈中的小孩编号%d\n",first.getNo());
     }