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

c语言解决
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
typedef struct ListNode ListNode;

//创造节点
ListNode* BuyListNode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

//创造环形链表
ListNode* CreatList(int n)
{
    //头节点
    ListNode* phead = BuyListNode(1);
    //尾节点
    ListNode* ptail = phead;
    for (int i = 2; i <= n; i++)
    {
        ptail->next = BuyListNode(i);
        ptail = ptail->next;
    }
    ptail->next = phead;
    return ptail;
}

int ysf(int n, int m ) 
{
    ListNode* prev = CreatList(n); //上一个节点
    ListNode* pcur = prev->next; //当前节点
    int count = 1; //报数
    while (pcur->next != pcur)
    {
        if (count == m)
        {
            //销毁pcur;
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        }
        else 
        {
            prev =pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return prev->val;
}