目录
前言
一.故事背景
二.题目
编辑三.思路
1）数组
编辑2） 循环链表
四.代码实现
搭配食用更佳哦~~
数据结构之单单单——链表-CSDN博客
数据结构之单链表的基本操作-CSDN博客
前面学了单链表的相关知识，我们来尝试做一下关于顺序表的经典算法题~
前言
这次是牛客上的一道题，是循环链表的经典应用，讲的是一个老六用自己的聪明才智躲过被杀的命运。
环形链表的约瑟夫问题_牛客题霸_牛客网 (nowcoder.com)
https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tpId=196&tqId=37145&ru=/exam/oj
一.故事背景
Josephus 问题是一个古老而著名的问题，最早的记载来自犹太历史学家弗拉维奥·约瑟夫斯（FlaviusJosephus），他在犹太战争中被罗马军队包围，为了不被俘虏，他和他的 39 个战友决定自杀，但是他们并不想自己亲手杀死自己，于是决定站在一个圆圈里，从一个人开始，每报数到第 14 个人，第 14 个人就会被杀掉，然后从下一个人开始重新报数，直到最后只剩下一个人，那个人就可以幸存。
二.题目
三.思路
1）数组
用数组的话我们需要先申请空间，然后再计数，每记到2就嘎掉它，可以给他赋值一个数组不存在的数比如 0 ，当报数到最后一个时我们需要返回数组最开始也就是下标为 0的时候，当剩下最后一个时就得到了活着的那一个，因为数组比较麻烦而且本篇要讲的是环形链表，所以这个代码就不写了，仅叙述一下思路
2） 循环链表
顾名思义，循环链表就是把原本线性的链表成环，如何实现呢？我们都知道链表尾节点指针指向NULL，所以我们把这个指针指向头节点就可以搞出一个循环链表。
和上一个思路一样，我们依旧让他们循环报数，报到 2 的嘎掉，在删除这个节点的同时我们需要将前一个节点的 next 指针指向被嘎节点的下一个指针，这样才能使链表连续起来
虽然画的蛮乱的，大致意思一样，最终结果就是第三个节点自己指向自己。
总结思路就两步：
- 创建带环链表
- 计数，嘎节点
四.代码实现
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @param m int整型
* @return int整型
*/
#include <stdlib.h>
typedef struct ListNode ListNode;
//创建节点
ListNode* buyNoded(int x){
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL) {
exit(1);
}
node->val = x;
node->next = NULL;
return node;
}
//创建带环链表
ListNode* createCircle(int n){
ListNode* phead = buyNoded(1);
ListNode* ptail = phead;
for (int i = 2; i<= n; i++) {
ptail->next = buyNoded(i);
ptail = ptail->next;
}
ptail->next = phead;
return ptail;
}
int ysf(int n, int m ) {
// write code here
//创建带环链表
ListNode* prev = createCircle(n);
ListNode* pcur = prev->next;
int count = 1;
//当链表中只有一个节点的情况
while (pcur->next != pcur) {
if (count == m) {
//销毁pcur节点
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
count = 1;
}else {
//此时不需要销毁节点
prev = pcur;
pcur = pcur->next;
count++;
}
}
//剩下的就是要返回的值了
return pcur->val;
}这道题到这就结束啦~虽然循环链表写起来比较麻烦要封装好多函数，但封装完就好写啦~~
🎈🎈完结撒花🎈🎈
