环形链表 - 《数据结构与算法》

1. 介绍

1. 介绍

使用单链表实现环形链表
需要注意的是：
- 需要让尾结点指向头节点，实现环状。
- 实现增删改查的时候，就需要注意遍历以指向最后一个结点，也就是头结点的上一个结点为止。 ```java class CircleLinkedList { /**
  - 链表的实现,需要的属性
  - 属性:
  - 1. 头节点
  - 方法:
  - 1. 构造方法初始化
  - 1. 添加节点(末尾直接添加,根据指定的方式进行添加)
  - 1. 删除节点
  - 1. 遍历链表
  - 1. 获取长度
  - 1. 根据编号进行节点的修改 / /*
  - 解决约瑟夫问题: / public CNode head; public CNode rear;
  CNode temp;
  
  // 1. 构造方法初始化 public CircleLinkedList(CNode head) { this.head = head; this.temp = head; CNode cur = head; while (cur.next != null) {
```
   cur = cur.next;
```
  } rear = cur; cur.next = head; }
  
  // 2. 添加节点(末尾直接添加,根据指定的方式进行添加) // 直接添加到尾部 public void add(CNode node) { CNode cur = head; rear.next = node; node.next = head; rear = node; }
  
  // 按编号顺序添加 public void addByOrder(CNode node) { CNode cur = head; while (cur != rear) {
```
   if (cur.no <= node.no && cur.next.no > node.no) {
       node.next = cur.next;
       cur.next = node;
       return;
   }
   cur = cur.next;
```
  } add(node); }
  
  // 3. 删除节点 public void delete(int no) { CNode cur = head; if (head.no == no) {
```
   while (cur != rear) {
       cur = cur.next;
   }
   cur.next = cur.next.next;
   head = cur.next;
   return;
```
  } while (cur != rear) {
```
   if (cur.next.no == no) {
       if (cur.next == rear) {
           cur.next = cur.next.next;
           rear = cur;
           return;
       }
       cur.next = cur.next.next;
       return;
   }
   cur = cur.next;
```
  } }
  
  // 4. 遍历链表 public void list() { CNode cur = head; while (cur != rear) {
```
   System.out.println(cur);
   cur = cur.next;
```
  } System.out.println(cur); }
  
  // 5. 获取长度 public int getLength() { CNode cur = head; int count = 1; while (cur != rear) {
```
   count++;
   cur = cur.next;
```
  } return count; }
  
  // 6. 根据编号进行节点的修改 public void update(CNode node) { CNode cur = head; while (cur != rear) {
```
   if (cur.no == node.no) {
       // 留着,如果放data域就可以进行使用
```
  // cur.data = node.data;
```
       return;
   }
   cur = cur.next;
```
  } }
  
  // 约瑟夫问题 public void josepfuDemo(int num,int k){ int n = getLength(); temp = rear; for (int i=0;i<num;i++){
```
   temp = temp.next;
```
  } for (int i=0;i<n;i++){
```
   josepfu(k);
```
  } } public void josepfu(int k){ for (int i=0;i<k-1;i++){
```
   temp = temp.next;
```
  } System.out.println(temp.next); delete(temp.next.no); }

}

class CNode { // 指针域 public CNode next; // data域 public int no;

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

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

}

<a name="AVY86"></a>
## 2. 解决约瑟夫问题

- 多个小孩子围成一圈，每隔几个进行出队一个孩子，然后在出队后的孩子中从刚才出队的位置继续进行出队，直到实现所有人都出队为止。
<a name="1EOg9"></a>
### 2.1 解决思路：

- 设定从第num个孩子开始，每走k步实现一次出队
- 指针从第num-1个结点出发
- 每走k-1步（因为单链表的删除需要辅助指针指向被删除结点的前一个结点，通过temp=temp.next.next实现删除），出队下一个结点
- 依次循环链表原长度次数
```java
    // 约瑟夫问题
    public void josepfuDemo(int num,int k){
        /**
         * 这里必须记录下length的值,如果在for循环中判断条件为i<getLength(),
         * 则每次进行判断时,会自动查找一个链表长度,而链表的长度一直在改变
         */
        int n = getLength();
        temp = rear;
        for (int i=0;i<num;i++){
            temp = temp.next;
        }
        for (int i=0;i<n;i++){
            josepfu(k);
        }
    }
    public void josepfu(int k){
        for (int i=0;i<k-1;i++){
            temp = temp.next;
        }
        System.out.println(temp.next);
        delete(temp.next.no);
    }