2024春晚纸牌魔术原理----环形链表的约瑟夫问题

一.题目及剖析

https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tab=note

这道题涉及到数学原理,有一般公式,但我们先不用公式,看看如何用链表模拟出这一过程

二.思路引入

思路很简单,就试创建一个单向循环链表,然后模拟报数,删去对应的节点

三.代码引入

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/#include <stdlib.h>
typedef struct ListNode ListNode ;ListNode* BuyNode(int x){ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->val = x;newNode->next = NULL;return newNode;}ListNode* createList(int n){ListNode* phead = BuyNode(1);ListNode* ptail = phead;for(int i = 2; i <=n; i++){ptail->next = BuyNode(i);ptail = ptail->next;}ptail->next = phead;return phead;}
int ysf(int n, int m ) {// write code hereListNode* head = createList(n);ListNode* prev = NULL;ListNode* pcur = head;int count = 1;while (pcur != pcur->next) {if(count == m){prev->next = pcur->next;free(pcur);pcur = prev->next;count = 1;}else{prev = pcur;pcur = pcur->next;count++;}}return pcur->val;
}