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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
 /*n=5,m=2
1 2 3 4 5
  -
1   3 4 5
      -
1   3   5
-
    3   5
        -
    3
    -
*/

#include <stdio.h>
#include<stdlib.h>
int ysf(int n, int m ) {
    // write code here
    if(n==0||m==0){
        return 0;
    }
    if(n==1){
        return 1;
    }
    struct ListNode* L=(struct ListNode*)malloc(sizeof(struct ListNode));
    L->next=NULL;
    struct ListNode* pre=L,*p=L,*tail=L;
    for(int i=0;i<n;i++){//建立环形链表
        struct ListNode* newNode=(struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val=i+1;//编号
        newNode->next=NULL;

        tail->next=newNode;
        tail=newNode;
    }
    tail->next=L->next;//除了头结点外形成链环
    p=tail->next;
    while(p->next!=p){//只剩一个结点时停止
        for(int i=0;i<(m-1)%n;i++){//移动m-1步
            pre=p;
            p=p->next;
        }
        pre->next=p->next;//删除结点
        free(p);
        n--;
        p=pre->next;//这里移动了1步
	  //一开始是想着从L出发每次移动m步，乍一看好像没问题，最后排查出来会出现原地踏步的情况(m%n==0)，删除结点后先移动一次，排除特殊情况
    }
    return p->val;
}