题解 | 环形链表的约瑟夫问题

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
#include<stdlib.h>

//开辟链表
typedef struct people
{
    int n;      //序号
    struct people* next;
}peo;

void kai_pi(peo*pe,int n)   //开辟大小为n的链表。
{
    peo* p = pe;            //保留头部指针。
    peo* newNode = NULL;
    int i = 2;              //链表的头部我提前开辟好了，所以从第2个开始添加。
    for (i = 2; i <= n; i++)
    {
        newNode = (peo*)malloc(sizeof(peo));
        if (newNode == NULL)
        {
            printf("开辟失败 \n");
            exit(1);
        }
        newNode->n = i;
        newNode->next = NULL;
        p->next = newNode;
        p = p->next;
    }
    p->next = pe;           //首尾相连成环。
    return;
}

void shan_chu(peo* pe, int n) //删除点到的成员。
{
    peo* p = pe;
    int i = 0;
    for (i = 0; i < n - 1; i++) //因为是环形，所以向后第n-1个就是他前面那个成员。
    {
        p = p->next;
    }
    p->next = pe->next;    
}

int ysf(int n, int m)
{
    peo pe;             //初始化头成员，因为至少有一个人。
    pe.n = 1;
    pe.next = NULL;

    peo* ppe = &pe;     //用指针用习惯了。
    kai_pi(ppe, n);

    while (n != 1)      //转圈找被点到的那个，把他踢出去，知道只剩1人，n=1;
    {
        
        int i = 1;      
        for (i = 1; i < m; i++)   
        {
            ppe = ppe->next;
        }
        shan_chu(ppe, n);
        ppe = ppe->next;  //找到被踢的那人的下一个人。

        n--;
    }
    return ppe->n;
}