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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
struct ListNode* buyNode(int x){
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node -> val = x;
    node -> next = NULL;
    return node;
}

struct ListNode* createCircle(int n){
    struct ListNode *phead =  buyNode(1);
    struct 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 ) {
    // write code here
    struct ListNode * prev = createCircle(n);
    struct 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;
}