当前位置：首页 > news >正文

c语言练习93：环形链表的约瑟夫问题

news 2025/8/18 17:28:26

环形链表的约瑟夫问题

环形链表的约瑟夫问题_牛客题霸_牛客网

描述

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

示例1

输入：

5,2

返回值：

说明：

开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3

示例2

输入：

1,1

返回值：

代码：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型* @param m int整型* @return int整型*/
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode ListNode ;
//创建结点
ListNode* ListBuyNode(int x) {ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL) {perror("malloc fail!");exit(1);}node->val = x;node->next = NULL;return node;
}
//创建带环链表
ListNode* CreatList(int n) {
//创建链表ListNode* phead = ListBuyNode(1);ListNode* ptail = phead;int i = 2;for (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 hereint count = 1;//刚开始的时候cur已经走到了套，头结点也会报数，所以count应该置为1//创建不带头的单向循环链表ListNode* prev = CreatList(n);//对链表进行约瑟夫游戏ListNode* cur = prev->next; //就是头结点while (cur->next != cur) {if (count == m) {prev->next = cur->next;free(cur);cur = NULL;cur = prev->next;count = 1;} else {prev = cur;cur = cur->next;count++;}}return cur->val;
}