目录
1.什么是循环链表？循环链表与单链表的区别?
? ? ? ? 循环链表是首尾相接的链表，普通链表是尾指针为空。
循环链表结构 一图胜千文
2.循环链表的应用有哪些？????????
? ? ? ? 约瑟夫环，报数游戏，现在k个人，1,2,3...n报数? 比如每次报2的出圈，然后重新报数。
? ? ? ? 解决方案:
? ? ? ? 方案1 标记+报数? 数组模拟
? ? ? ? 方案2 使用循环链表模拟报数
?第一次出局? 2? 4
?第二次出局? 1??5
第三次只有一个元素3? 循环退出
代码如下
public static void main(String[] args) {
//方法1:使用标记+报数器
// int num = GetLastIndex(5,2);
//方法2:使用循环链表 正确的返回结果是2
int num = GetLastIndex2(5, 2);
System.out.println(num);
}
//标记+报数器
//初始化数组 每个元素都是1
/**
* @Description:
* @Date: 2021/8/9 18:54
* @Author: fuguowen
* @Return k个人的索引的下标 比如2代表第三个人
* @Throws
*/
public static int GetLastIndex(int k, int p) {
//k个人
//p报2
int[] arr = new int[k];
//初始化数组都为1
for (int i = 0; i < arr.length; i++) {
arr[i] = 1;
}
int num = arr.length;
//报数器
int flag = 0;
while (num > 1) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
flag++;
if (flag == p) {
//数组清空
arr[i] = 0;
//报数器清空
flag = 0;
//数量减一
num--;
}
}
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
return i;
}
}
return 0;
}
//使用循环链表模拟，报数的人删除对应的节点
public static int GetLastIndex2(int k, int reportNum) {
//k个人
//构建循环链表
Node head = CreatCycLinkedList(k);
Node p = head.next;
//队列中元素只有一个的情况是p.next=p ☆☆☆☆☆
while (p.next != p) {
//p.next指向当前要删除的元素
for (int i = 0; i < reportNum; i++) {
p = p.next;
}
//删除元素
p.next = p.next.next;
//指针下移
p.next = p;
}
return p.next.index;
}
public static Node CreatCycLinkedList(int k) {
//构建循环链表
Node head = new Node(-1);
Node cur = head;
for (int i = 0; i < k; i++) {
cur.next = new Node(i);
cur = cur.next;
}
cur.next = head.next;
return head;
}
// 参考:
// 1.https://www.cxyxiaowu.com/1159.html
public class Node {
int index;
Node next;
public Node( int index) {
this.index = index;
}
}3.总结?
? ? ? 循环链表的主要应用在约瑟夫环，报数游戏，golang chan底层的数据节后也是循环链表等。它与单链表的区别是循环链表是尾指针指向头指针。普通单链表是尾指针指向null.
4.参考
1.https://www.cxyxiaowu.com/1159.html
? ? ?我是厚积薄发，?您的一键三连是我最大的创作动力，请一键三连，如有问题，请留言。