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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
 typedef struct ListNode ListNode;
 //创建节点
 ListNode*buynode(int n)
 {
    ListNode*newnode=(ListNode*)malloc(sizeof(ListNode));
    if(newnode==NULL)
    {
        exit(1);
    }
    newnode->next=NULL;
    newnode->val=n;
    return newnode;
 }
 //创建环形链表
 ListNode*creatCircle(int n)
 {
    ListNode*phead=buynode(1);
    ListNode*ptail=phead;
    //尾插
    for(int i=2;i<=n;i++)
    {
        ptail->next=buynode(i);
        ptail=ptail->next;
    }
    //首尾相连
    ptail->next=phead;
    return ptail;//返回头还是尾取决于接下来怎么用
 }
int ysf(int n, int m ) 
{
    ListNode*prev=creatCircle(n);
    ListNode*pcur=prev->next;
    int count=1;
    while(pcur->next!=pcur)//只有一个节点循环结束
    {
        if(count==m)//销毁节点
        {
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;//重新报数
        }
        else
        {
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    return pcur->val;
}