【数据结构】_链表经典算法OJ：环形链表的约瑟夫问题

目录

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){
            //销毁curNode
            prevCurNode->next=curNode->next;
            free(curNode);
            curNode=prevCurNode->next;
            count=1;
        }else{
            // 无需销毁curNode
            prevCurNode=curNode;
            curNode=curNode->next;
            count++;
        }
    }
    // 剩下的唯一一个结点就是留下的编号
    return curNode->val;
}

注：

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

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

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