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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
 typedef struct ListNode ListNode;
 //创建节点函数
 ListNode* buynode(int x){
    ListNode* node=(ListNode*)malloc(sizeof(ListNode));
    if(node==NULL){
        exit(1);
    }
    node->val=x;
    node->next=NULL;
    return node;
 }
 //创建带环链表函数
 ListNode* createCircle(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;
 }
 //n是总人数
 //m：报到m的人离开
int ysf(int n, int m ) {
    //1.根据n创建带环链表
    int count=1;//报的数
    //头节点的前一个节点
    ListNode* prev=createCircle(n);
    //头节点
    ListNode* pcur=prev->next;
    while(pcur!=pcur->next){
        //此种情况要销毁pcur节点
        if(count==m){
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;//此时pcur走向了下一轮报数的新节点
        }
        //此种情况不需要销毁pcur节点
        else{
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    return pcur->val;
}