单向环形链表应用场景

单向环形链表应用场景

Josephu(约瑟夫、约瑟夫环) 问题

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

可以用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。

分析

假设有n = 5 , 即有5个人 k = 1, 从第一个人开始报数 m = 2, 数 2 下
则出圈的顺序为：2->4->1->5->3

构建一个单向的环形链表思路
- 1. 先创建第一个节点, 让 first 指向该节点，并形成环形；
- 1. 后面当我们每创建一个新的节点，就把该节点加入到已有的环形链表中即可；
遍历环形链表
- 1. 先让一个辅助指针(变量) curBoy，指向 first 节点；
- 1. 然后通过一个 while 循环遍历该环形链表即可，直到curBoy.next == first 结束；
出圈：根据用户的输入，生成一个小孩出圈的顺序
- 创建一个辅助变量 helper，初始指向环形链表的最后一个节点
- 报数前，让 first 和 helper 移动 k-1 次
- 当报数时，让 first 和 helper 同时移动 m-1 次；
- 让 first 出圈：first = first.next; helper.next = first;
  实现
  节点对象
```java package com.zsy.datastructure.linkedlist.circlelinklist;

/**

@author zhangshuaiyin
@date 2021-04-12 16:25 */ public class Boy { int no; Boy next; public Boy(int no) {
```
 this.no = no;
```
} } ```
单向环形链表
```java package com.zsy.datastructure.linkedlist.circlelinklist;

/**

单向环形链表解决约瑟夫问题
小美有一天想玩丢手绢，但是TA就一个人怎么办呢？ *
@author zhangshuaiyin
@date 2021-04-12 16:26 */ public class CircleSingleLinkedList { private Boy first = new Boy(1);

/**
- 向约瑟夫环添加成员 *
- @param nums 成员个数 */ public void init(int nums) { if (nums < 2) {
```
 throw new RuntimeException("成员个数必须大于1");
```
  } Boy temp = first; for (int i = 2; i <= nums; i++) {
```
 Boy boy = new Boy(i);
 temp.next = boy;
 boy.next = first;
 temp = boy;
```
  } }
  
  /**
- 遍历链表查看元素 */ public void list() { Boy temp = first; System.out.print(“小孩的编号: “); do {
```
 System.out.printf("%d\t", (temp.no));
```
  } while ((temp = temp.next) != first); }
  
  /**
- 根据用户的输入，计算小孩出圈的顺序 *
- @param startNo 从第几个小孩开始报数
- @param count 报数次数
- @param nums 小孩个数 */ public void remove(int startNo, int count, int nums) { if (startNo < 1 || startNo > nums) {
```
 throw new RuntimeException("参数输入有误~");
```
  } // 创建辅助变量helper，初始指向环形链表的最后一个节点 Boy helper = first; while (helper.next != first) {
```
 helper = helper.next;
```
  } // 报数前，先让 first 和 helper 移动第一个报数小孩的前一个位置 for (int i = 0; i < startNo - 1; i++) {
```
 first = first.next;
 helper = helper.next;
```
  } // 开始报数，helper == first 说明只剩一个成员 while (helper != first) {
```
 // 让 first 和 helper 移动 报数次数-1 次，这时 first 就是要出圈的小孩
 for (int i = 0; i < count - 1; i++) {
     first = first.next;
     helper = helper.next;
 }
 System.out.printf("小孩%d 出圈\n", first.no);
 //这时将 first 指向的小孩节点出圈
 first = first.next;
 helper.next = first;
```
  } System.out.printf(“小孩%d 出圈\n”, first.no); } } ```
  测试
```java package com.zsy.datastructure.linkedlist.circlelinklist;

/**

@author zhangshuaiyin

@date 2021-04-12 16:44 */ public class JosephusTest { public static void main(String[] args) {

 CircleSingleLinkedList circleLinkedList = new CircleSingleLinkedList();
 circleLinkedList.init(5);
 circleLinkedList.list();
 System.out.print("\n-----------出圈-------------\n");
 circleLinkedList.remove(1, 2, 5);

} } ```

环形链表

单向环形链表应用场景

Josephu(约瑟夫、约瑟夫环) 问题

分析

实现

节点对象

单向环形链表

测试