目录
题目
描述
示例1
示例2
图解
代码(解析在注释中)
题目
描述
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
数据范围： 1≤�,�≤100001≤n,m≤10000
进阶：空间复杂度 �(1)O(1)，时间复杂度 �(�)O(n)
示例1
输入：
5,2
返回值：
3
说明：
开始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
1图解
代码(解析在注释中)
/*** 定义一个结构体 ListNode，用于表示链表节点*/
typedef struct ListNode ListNode;/*** 创建一个新的链表节点，并将其值初始化为给定整数 x。** @param x 初始化节点值的整数* @return 新创建的 ListNode 类型指针*/
ListNode* New_node(int x) {ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 分配内存空间if (node == NULL) { // 检查内存分配是否成功exit(1); // 若失败则退出程序}node->next = NULL; // 初始化 next 指针为空node->val = x; // 设置节点值return node; // 返回新创建的节点指针
}/*** 根据给定整数 n 创建一个包含 n 个节点的环形链表，* 节点值从 1 到 n 依次递增。** @param n 链表中节点的数量（整数）* @return 环形链表的尾节点指针*/
ListNode* Link(int n) {ListNode* head = New_node(1); // 创建头节点ListNode* tail = head;// 循环创建并连接后续节点for (int i = 2; i <= n; i++) {tail->next = New_node(i);tail = tail->next;}// 将尾节点与头节点相连形成环形链表tail->next = head;return tail;
}/*** 删除环形链表中每 m 个节点中的倒数第二个节点，直到只剩下一个节点为止。* 最后返回该单个节点的值。** @param n 环形链表中原始节点的数量（整数）* @param m 每隔几个节点删除一次倒数第二个节点（整数）* @return 剩余单个节点的值（整数）*/
int ysf(int n, int m) {ListNode* prev = Link(n); // 创建并初始化环形链表ListNode* pcur = prev->next;int count = 1;// 遍历链表，直到只剩下一个节点while (pcur->next != pcur) {if (count == m) {prev->next = pcur->next; // 删除倒数第二个节点free(pcur);pcur = prev->next; // 更新 pcur 指向下一个有效节点count = 1;} else {prev = pcur;pcur = pcur->next;count++;}}// 销毁最后一个节点前获取其值int var = prev->val;// 释放最后一个节点内存free(prev);prev = NULL;return var; // 返回最后一个节点的值
}
