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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @param m int整型
 * @return int整型
 */
#include <stdio.h>
#include <stdlib.h>
// typedef struct ListNode {
//     int val;
//     struct ListNode* next;
// } ListNode;

typedef struct ListNode ListNode;
ListNode* CreateNode(int x) {
    //创建节点
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL) {
        printf("创建新节点失败\n");
        exit(-1);
    }
    node->val = x;
    node->next = NULL;
    return node;
}
//创建环型链表
ListNode* Circularlist(int x) {
    if (x <= 0) {
        exit(-1);
    }
    ListNode* phead = CreateNode(1);//创建头节点
    ListNode* tail = phead;
    for (int i = 2; i <= x; i++) {
        tail->next = CreateNode(i);
        tail = tail->next;//更新tail节点
    }
    tail->next = phead;
    return tail;
}
int ysf(int n, int m ) {
    ListNode* pcur = Circularlist(n);//创建环形链表并返尾指针
    ListNode* prev = pcur->next;//得到头指针
    ListNode* pointer = NULL;
    int count = 1;//计数器
    while (prev->next != prev) {
        //如果计算器等于a
        if (count == m) {
            pointer = prev;//保存该指针
            prev = prev->next;//将该指针指向下一个节点
            pcur->next = prev;//移除该指针
            free(pointer);//释放该指针
            count = 1;
        } else {
            pcur = prev;
            prev = prev->next;
            count++;
        }
    }
    return prev->val;
}