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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
struct ListNode* ListInit(struct ListNode* head, int x) {
    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newnode->val = x;
    head->next = newnode; newnode->next = NULL;
    return newnode;
}
struct ListNode* del(struct ListNode* head, int m) {
    struct ListNode* prev = NULL;
    for (int i = 1; i < m; i++) {
        prev = head;
        head = head->next;
    }
    prev->next = head->next;
    free(head); head = NULL;
    return prev->next;
}
int ysf(int n, int m) {
    if (n == 1) return 1;
    else {
        struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));// write code here
        struct ListNode* pcur = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* next;
        pcur->val = 1; head->next = pcur;
        for (int i = 1; i < n; i++) {
            ListInit(head->next, i + 1);
            head->next = head->next->next;
        }
        head->next->next = pcur;
        if (m == 1) return head->next->val;
        else {
            for (int i = 0; i < n - 1; i++) {
                pcur = del(pcur, m);
            }
            return pcur->val;
        }
    }
}