1.6 单向环形链表和约瑟夫问题

基本介绍
- 单向循环链表和单向链表基本一样，尾节点的next指向第一个节点
- 当链表中只有一个节点时，该节点的next指向本身
约瑟夫问题
- 基本介绍
  - 设编号为 1，2，… n 的n个人围坐一圈，约定编号为 k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
  - 例如：编号为1,2,3,4,5 从1开始，数2次，则出队编号为2,4,1,5,3
- 实现思路
  - 采用单向环形链表，将数到那个节点在环形链表中删除后，重新构建环形链表，直到剩下最后一个节点
  - 由于采用的单向链表，所以需要两个指针，current指向当前的节点（也就是要出队的节点，初始值为head节点），currentBefore指向当前节点的前一个节点（用来删除当前节点，初始值为head节点的前一个节点）
  - 将两个节点同时移动k-1次，第一次的报号位置，由于本身也要报号，所以k-1次（两个指针必须相连，且current在后）
  - 开始报号，将两个节点同时移动k-1次（原理同上）
  - 出队current = current.next; currentBefore = current;
  - 当current == currentBefore; 队列中就只剩下了一个节点（结束）
代码实现

public class CircleSingleLinkedListDemo {
   public static void main(String[] args) {
       CircleSingleLinkedLis circleSingleLinkedLis = new CircleSingleLinkedLis();
       // 创建并显示单向环形链表
       circleSingleLinkedLis.create(10);
       circleSingleLinkedLis.show();
       // 实现约瑟夫问题
       System.out.println("---约瑟夫问题---");
       circleSingleLinkedLis.josephu(5, 10, circleSingleLinkedLis.size());
   }
}
// 单向环形链表类
class CircleSingleLinkedLis {

   private Children head; // 头节点，将加入的第一个节点作为头节点（不能动，在约瑟夫环中可以动）

   // 创建单向环形链表(参数为有几个节点)
   public void create(int number) {
       if (number < 2) {
           System.out.println("至少两个节点");
           return;
       }
       Children current = null; // 尾指针 指向下一个节点为头节点的节点（方便插入，不需要每次都遍历）
       for (int i = 1; i <= number; i++) { // i作为节点的编号
           Children children = new Children(i);
           if (null == head) { // 第一个节点 自己指向自己 单独处理也是为了防止空指针
               head = children;
               children.next = head;
               current = head;
           } else { // 先将当前节点的下一个节点指向要添加的节点，再后移当前节点，再将当前节点的下一个节点指向头节点
               current.next = children;
               current = current.next;
               children.next = head;
           }
       }
   }

   // 显示单向环形链表
   public void show() {
       if (null == head) {
           System.out.println("单向环形链表为空");
       }
       Children temp = head;
       while (null != head) {
           System.out.println(temp);
           temp = temp.next; // 后移节点
           if (temp == head) {
               break; // 到头节点了 退出
           }
       }
   }

   // 获取链表节点个数
   public int size() {
       int sum = 0;
       Children temp = head;
       while (null != temp ) {
           sum++;
           temp = temp.next;
           if (temp == head) {
               break;
           }
       }
       return sum;
   }
   
   /**
    * 约瑟夫问题实现（一群小孩围在一起，由第k个小孩报n下数，停止报数的那个小孩出圈，问小孩出圈的顺序）
    * 采用两个指针（一个指向当前报数的孩子，另一个指向报数孩子的前一个孩子，因为单链表删除必须拿到当前节点的前一个节点）
    * @param start 开始报数的节点
    * @param count 报多少下
    * @param size 总共有多少个小孩(此处不能大于链表的有效个数)
    */
   public void josephu(int start, int count, int size) {
       if (null == head || start < 1 || start > size || size > this.size()) {
           System.out.println("输入的数据不合法");
           return;
       }
       Children current = head; // 当前节点
       Children currentBefore = current; // 当前节点的前一个节点
       while (currentBefore.next != head) { // 寻找当前节点的前一个节点
           currentBefore = currentBefore.next; // 指针后移
       }
       for (int i = 0; i < start - 1; i++) { // 将两个指针移动到起始位置 例 1 -> 3 需移动2次 则是 start - 1
           current = current.next;
           currentBefore = currentBefore.next;
       }
       while (current != currentBefore) { // 如果圈中只剩一个小孩 则两个指针重合
           // 从起始位置报数 由于起始节点本身也要报数 则是移动 count - 1
           for (int i = 0; i < count - 1; i++) {
               current = current.next;
               currentBefore = currentBefore.next;
           }
           // 报数完毕 移除当前节点 并重新构建链表
           System.out.println(current);
           current = current.next; // 后移当前指针
           currentBefore.next = current; // 重新构建链表
       }
       System.out.println(current); // 输出圈中最后一个节点的信息
   }

}
// 链表节点类
class Children {
   public int no;
   public Children next; // 指向下一个节点

   public Children(int no) {
       this.no = no;
   }

   @Override
   public String toString() {
       return "Children{" +
               "no=" + no +
               '}';
   }
}