环形链表的约瑟夫问题

这道题思路如下:

1.首先按照题目要求，要创建一个链表

2.要把链表头尾向连，形成带环链表

3.遍历链表，建立一个指针pcur指向当前节点，再建立一个指针prev指向pcur指的节点的前一个节点，当要删除pcur的时候，只需要让prev->next = pcur->next,这样子就跳过了pcur，再将pcur给free掉就好了，如此循环，最后只剩一个值

1.先来创建链表

首先重命名一下，方便表达：

接着就要创建链表了，但是我们还没有节点，所以先要自己写一个函数buynode()，用于创立节点，使用malloc开辟节点，然后检查是否开辟成功，如果成功就给节点传数据，代码如下:

创建完节点以后，就可以来创建链表了:

1.创建一个指针phead指向头结点，创建一个尾指针ptail，用ptail遍历数组，最后将ptail的next指针指向头结点，实现环形链表:

2.前置准备完毕，开始做题，首先我们需要两个指针，一个prev，一个pcur；pcur指向头结点，prev指向pcur的前一个节点，由于现在已经是环形链表，所以prev指向的就是尾节点，接着给一个count来数数：

接下来写一个循环，每次都count++，那如果count达到了题目限制的m，就删那个pcur，并且在free之前，要记得先把prev和pcur->next连起来，如果count没有达到限制的m，就正常往后走。

这样子循环的话，n的值会越来越小，那知道达到这个链表只有一个节点的时候，才符合题意，也就是while(pcur!=pcur->next)，代码如下:

最后按照题意，返回val:

整体代码如下:

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/
typedef struct ListNode LSTNode;//重命名方便表示
//创建节点
LSTNode* buynode(int x)
{//先用malloc开辟一块空间LSTNode* node=(LSTNode*)malloc(sizeof(LSTNode));if(node==NULL)//判断一下有没有开辟成功{exit(1);}node->val = x;//给新开辟的节点赋值node->next = NULL;return node;//返回节点a
}
//创建带环链表
LSTNode* createcircle(int n)
{//先创建头结点和尾节点LSTNode *phead = buynode(1);//用buynode函数LSTNode *ptail = phead;for(int i = 2 ; i <= n ; i++){ptail->next=buynode(i);ptail=ptail->next;}ptail->next = phead;return ptail;
}
int ysf(int n, int m ) {// write code here//根据n创建带环链表LSTNode* prev = createcircle(n);//头结点的前一个节点的指针LSTNode* pcur = prev->next;//指向头结点的指针int count=1;//计数while(pcur->next != pcur)//当链表只有pcur自己一个节点的时候，跳出循环{if(count == m)//到达规定的数字,删除这个节点{prev->next = pcur->next;//跳过pcurfree(pcur);//将pcur的节点删掉pcur = prev->next;//pcur向前移动count = 1;//count重新变为1}else{//此时不需要销毁节点prev = pcur;pcur = pcur->next;count++;}}//此时只剩下一个节点return pcur->val;
}