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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
typedef struct ListNode LN;

struct ListNode* creatNode(int n)
{
    LN* newNode=(LN*)malloc(sizeof(LN));
    newNode->val=n;
    newNode->next=NULL;
    return newNode;
}

LN* creatCircle(int n)
{
    LN*phead=creatNode(1);//创建第一个节点
    LN*pcur=phead;
    int i=2;
    LN*newNode;
    while(i<=n)
    {
        newNode=creatNode(i++);
        pcur->next=newNode;
        pcur=pcur->next;
    }
    pcur->next=phead;
    return phead;
}

int ysf(int n, int m ) {
    // write code here
    int count=0;//报数的序号
    int peopleCount=n;
    LN*head=creatCircle(n);//创建环形链表
    LN*pcur=head;
    LN*prev=head;
    while(prev->next->val!=1)//找到尾节点
    {
        prev=prev->next;
    }
    while(1)
    {
        count++;
        if(count==m)//报到m删除节点
        {
            if(peopleCount==2)
            {
                return prev->val;
            } 
            prev->next=pcur->next;
            count=0;
            peopleCount--;
            pcur=pcur->next;
        }
        else 
        {
            pcur=pcur->next;
            prev=prev->next;
        }
        
    }
}