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

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

OJ链接

思路：

• 创建带环链表
• 带环链表的删除节点

代码如下：

#include<stdlib.h>typedef struct ListNode ListNode;
ListNode* ListBuyNode(int x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));node->val = x;node->next = NULL;return node;
}
//创建带环链表
ListNode* CreateList(int n)
{ListNode* phead = ListBuyNode(1);ListNode* ptail = phead;for (int i = 2; i<=n; i++) {ListNode* node = ListBuyNode(i);ptail->next = node;ptail = ptail->next;}//以上只是创建单链表//将首尾相连ptail->next = phead;//有尾结点就能找到头结点return ptail;
}int ysf(int n, int m ) {// write code here//不带头带环单向循环链表ListNode* prev = CreateList(n);//对改链表进行游戏ListNode* cur = prev->next;int count = 1;//报数while(cur->next!=cur){if(count == m){//删除节点prev->next = cur->next;free(cur);cur = prev->next;count = 1;}else{//继续报数prev = cur;cur = cur->next;count++;}}//此时链表就剩下一个节点了return cur->val;
}