NowCoder | 环形链表的约瑟夫问题
思路:
- 创建带环链表
- 带环链表的删除节点
代码如下:
#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; }