目录

1. 题目链接及描述

2. 解题思路

3. 程序

---

1. 题目链接及描述

题目链接：环形链表的约瑟夫问题_牛客题霸_牛客网

题目描述：

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

数据范围： 1≤n,m≤10000
进阶：空间复杂度O(1)，时间复杂度O(n)；

附：关于约瑟夫问题：

2. 解题思路

总思路：

创建一个环形链表以示当前的n个人，创建指针变量curNode用于遍历链表。创建计数变量count对应遍历的结点，每遍历一个结点则count自增1。当count从1自增到m时，销毁curNode当前指向的结点。从下一结点开始重新遍历，并将count重置为1重新开始递增。

具体实现思路：

为了销毁curNode且保证环形链表的链接，还需记录curNode的前驱结点，记为prevCurNode，每销毁当前的curNode，就令prevCurNode->next=curNode->next；

可通过题目示例辅助思考：

3. 程序

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/
typedef struct ListNode ListNode;
// 创建结点
ListNode* CreateNode(int x){ListNode* node=(ListNode*)malloc(sizeof(ListNode));if(node==NULL){exit(1);}node->val=x;node->next=NULL;return node;
}
// 创建n结点的带环链表
ListNode* createCircle(int n){// 先创建n结点的单向链表ListNode* phead=CreateNode(1);ListNode* ptail=phead;for(int i=2; i<=n; i++){ptail->next=CreateNode(i);ptail=ptail->next;}// 再链首尾ptail->next=phead;return ptail;
}
int ysf(int n, int m ) {ListNode* prevCurNode=createCircle(n);ListNode* curNode=prevCurNode->next;int count=1;// 当链表仅剩1个结点时结束while(curNode->next!=curNode){if(count==m){//销毁curNodeprevCurNode->next=curNode->next;free(curNode);curNode=prevCurNode->next;count=1;}else{// 无需销毁curNodeprevCurNode=curNode;curNode=curNode->next;count++;}}// 剩下的唯一一个结点就是留下的编号return curNode->val;
}

注：

（1）关于创建环形链表的返回值问题，由于要求的m为未知数，故对于每一个遍历的结点都需保留其前驱结点。创建环形链表完成后，由于是从phead开始计数，若返回phead，则导致无法定位其前驱结点，此种情况若m=1则会出错。故CreateCircle函数应该返回ptail而非phead；

（2）关于判定的截止条件：

由于只求最后一个留下的人的编号，故最后一轮时，整个环形链表只剩一个结点。可令循环结束条件为curNode->next == curNode；