前言

题目描述：

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

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

n-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

一、用循环链表实现

typedef struct Node
{int id;  // 编号（从 1 开始）struct Node* next;
}Node;int ysf(int n, int m) 
{// 采用尾插法构造编号为 1 ~ n 的循环链表Node* phead = (Node*)malloc(sizeof(Node));  // 头指针phead->id = 1;Node* tail = phead;  // 尾指针for (int i = 2; i <= n; ++i){Node* newnode = (Node*)malloc(sizeof(Node));newnode->id = i;newnode->next = NULL;tail->next = newnode;tail = newnode;}tail->next = phead;  // 让最后一个节点的 next 域指向第一个节点// 开始Node* cur = phead;Node* prev = tail;int count = 1;  // 计数器while (cur != prev){if (count == m){prev->next = cur->next;free(cur);cur = prev->next;count = 1;  // 重置为 1}else {prev = cur;cur = cur->next;++count;}}int ret = cur->id;free(cur);return ret;
}

二、用数组实现

int ysf(int n, int m)
{int* is_out = (int*)calloc(n, sizeof(int));  // 0 表示在圈内，1 则表示退出int number = n;int count = 1;  // 计数器int i = 0;while (number > 1){if (is_out[i] == 0)  // 圈内的人报数{if (count == m){is_out[i] = 1;  // 退出--number;count = 1;  // 重置为 1}else{++count;}}// 法一：++i;if (i >= n){i = 0;}// 法二：// i = (i + 1) % n;}for (i = 0; i < n; ++i){if (is_out[i] == 0){break;}}free(is_out);  // 释放动态开辟的内存空间return i + 1;  // 返回编号
}

三、用数组模拟链表实现

int ysf(int n, int m)
{int* next = (int*)calloc(n, sizeof(int));for (int i = 0; i < n - 1; ++i){next[i] = i + 1;}// next[n - 1] == 0int cur = 0;int prev = n - 1;int count = 1;  // 计数器while (cur != prev){if (count == m){next[prev] = next[cur];next[cur] = -1;  // 退出cur = next[prev];count = 1;  // 重置为 1}else{prev = cur;cur = next[cur];++count;}}free(next);  // 释放动态开辟的内存空间return cur + 1;  // 返回编号
}