环形链表的情况就更为特殊了，它是一个环状的，所以就跟我们之前的基本操作就不太一样了
这里讲的是单向约瑟夫环
丢手绢大家都知道吧，这就是约瑟夫环，本文以此为例

要求：
一个 n 个小朋友
从第k个小朋友开始报数，（开始的小朋友报1，下一个小朋友报2）
比如报m个数，那么 报的数为m的小朋友出列
给出小朋友出队的顺序。

例子🌰：
一共5个小朋友
从第一个小朋友开始数，数2个数就可以了，那么它的出队顺序为 2，4，1，5，3
如图：
约瑟夫环.gif

思路：
需要两个辅助节点，first 和 helper
first 是开始报数的小朋友
helper是它前边的一个节点，代表一个环里最后的一个小朋友。

在报数的时候，first = first.next, helper = helper.next，两个节点都要后移
在让小朋友出对的时候（删除节点），first 要再后移一次，first = first.next
然后 helper.next = first

约瑟夫环节点结构

  1. class Boy {
  2.     private int no;
  4.     private Boy next;
  6.     public Boy(int no) {
  7.         this.no = no;
  8.     }
  10.     public int getNo() {
  11.         return no;
  12.     }
  14.     public void setNo(int no) {
  15.         this.no = no;
  16.     }
  18.     public Boy getNext() {
  19.         return next;
  20.     }
  22.     public void setNext(Boy next) {
  23.         this.next = next;
  24.     }
  26.     @Override
  27.     public String toString() {
  28.         return "Boy [no=" + no + "]";
  29.     }
  32. }

基本操作

添加

添加的要注意一点，当只有一个节点时，它的next域指向自己，也形成一个环
如果不止一个节点时，next指向下一个，然后最后一个节点的next指向第一个

思路：
first 节点用来指向 第一个小孩节点
一个辅助接点 curBoy 用来指向遍历后的最后一个节点

如果是第一个节点时，first.next = first,此时 curBoy 也为 first
其余的时候新加节点 boy
最后一个节点next指向新节点
curBoy.next = boy

新节点next 指向第一个节点
boy.next = first;

curBoy 也后移
curBoy = boy

  1.      //第一个小孩节点
  2.     private Boy first = null;
  3.     //添加小孩，构成环形链表
  4.     public void add(int nums) {
  5.         //如果nums < 1 不允许，至少要有一个
  6.         if (nums < 1) {
  7.             System.out.println("nums 值不正确");
  8.             return;
  9.         }
  11.         //辅助节点
  12.         Boy curBoy = null;
  14.         //使用循环来创建环形链表
  15.         for (int i = 1; i <= nums; i++) {
  16.             //根据编号，创建小孩节点
  17.             Boy boy = new Boy(i);
  18.             //如果是第一个小孩
  19.             //这比较特殊，它可以与自己构成环
  20.             if (i == 1) {
  21.                 first = boy;
  22.                 first.setNext(first);
  23.                 //curBoy指向第一个小孩
  24.                 curBoy = first;
  25.             } else {
  26.                 //curBoy 指向新节点
  27.                 curBoy.setNext(boy);
  28.                 boy.setNext(first);
  29.                 //curBoy 后移一下
  30.                 curBoy = boy;
  31.             }
  32.         }
  33.     }

遍历

遍历的时候，只需要判断 curBoy.next 是否与 frist 相当，如果相等，说明，已经遍历了一次环

  1.     //遍历当前的环形链表
  2.     public void list() {
  3.         if (first == null) {
  4.             System.out.println("链表为空");
  5.             return;
  6.         }
  8.         Boy curBoy = first;
  10.         while(true) {
  11.             System.out.println(curBoy);
  12.             if( curBoy.getNext() == first) {
  13.                 break;
  14.             }
  16.             //curBoy 后移
  17.             curBoy = curBoy.getNext();
  18.         }
  19.     }

获得出队顺序

思路：
startNo 开始报数的人，count 报数到第几个数，nums 一共有多少个小朋友
需要两个辅助节点，first 和 helper
first 是开始报数的小朋友
helper是它前边的一个节点，代表一个环里最后的一个小朋友。

首先要先让helper 指向环中最后一个节点
然后让 first 指向 startNo这个开始报数的小朋友，
(Ps: 其实这两步可以合二为一，先让 helper = first，然后再让 first = first.next 可以达到同样的效果，不然时间复杂度太高了，但是注意，从第一个小朋友开始的时候不适用，可以单独判断一下)

然后开始报数，也就是遍历 count -1 次，因为开始的小朋友也报数，
在报数的时候，first = first.next, helper = helper.next，两个节点都要后移
在让小朋友出对的时候（删除节点），first 要再后移一次，first = first.next
然后 helper.next = first

最后当 first == helper的时候，说明这是环中的最后一个节点
直接输出就行了

  1.     //获取出队顺序
  2.     //startNo 开始报数的人，count 报数到第几个数，nums 一共有多少个小朋友
  3.     public void popNums(int startNo, int count, int nums) {
  4.         if (first == null || startNo < 1 || startNo > nums || nums < 1) {
  5.             System.out.println("参数有误");
  6.             return;
  7.         }
  9.         //指向最后一个节点
  10.         Boy helper = first;
  12.         if (startNo == 1) {
  13.             while(true) {
  14.                 if( helper.getNext() == first) {
  15.                     break;
  16.                 }
  18.                 //curBoy 后移
  19.                 helper = helper.getNext();
  20.             }
  21.         }
  24.         //移动开始报数的那个小孩的位置
  25.         for(int i = 0; i < startNo -1; i++) {
  26.             helper = first;
  27.             first = first.getNext();
  28.         }
  30.         while(true) {
  31.             //说明圈中只有一个节点
  32.             if(helper == first) {
  33.                 break;
  34.             }
  36.             for(int i = 0; i < count - 1; i++) {
  37.                 first = first.getNext();
  38.                 helper = helper.getNext();
  39.             }
  41.             System.out.println(first+": 出圈");
  43.             //出圈后，删除这个节点
  44.             first = first.getNext();
  45.             helper.setNext(first);
  46.         }
  48.         System.out.println(first+": 最后出圈");
  49.     }