约瑟夫环上机题全解析：从循环链表到递推公式的调试复盘

上周帮学弟调试上机实践的作业，清单里编号2.3.4这道题，一眼看去就是经典的约瑟夫环：n个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1报数，直到最后一人出圈，要求输出完整的出圈顺序。学弟卡了很久，本地样例能过，放在在线评测平台上要么超时，要么直接段错误。我把这道题完整拆了一遍，从最直观的循环链表、数组标记，到最后的数学递推，顺便把调试过程中遇到的几个典型问题也记录下来。这篇文章就当作一次上机实践复盘，给正在刷这类题的人一个参考。

题目编号虽然叫2.3.4，但它背后的知识密度远比看着大。一个人能不能写好这道题，基本能看出他对数据结构和边界条件的掌握程度。下面我会按实际做题的顺序来讲：先拆题，再给三种解法和完整代码，最后是调试实录和上机习惯。

1. 拿到题目2.3.4，先别急着敲代码

1.1 题目到底在问什么

上机实践题最容易犯的错误就是读题太快。2.3.4这道题，表面描述很常见：一堆人围成圈，报数，报到指定数字的人出圈，循环往复，直到所有人出列。但这里有个关键分叉，题目到底要你输出什么？是每一轮出圈的完整顺序，还是最后剩下的那个人？

我让学弟把原题截图发过来，才发现题面里写的是"输出出圈顺序，空格分隔"。这直接决定了下面用什么算法。如果只问最后幸存者，数学递推一行就能算出答案；如果要输出完整的出圈顺序，那模拟过程基本躲不掉，只能考虑模拟的常数和数据结构优化。很多人一看到围成一圈就条件反射写循环链表，结果题目可能只想考递推；也有些人没注意到要输出全序列，直接用递推公式交上去，样例自然就错了。

所以拿到上机题第一步不是打开IDE，而是把题目里的输入输出要求圈出来。你需要确认三件事：第一，输入是两个整数n和m，还是有多组测试数据；第二，编号是从1开始还是从0开始；第三，输出是"每行一个出圈编号"还是"空格分隔且行尾没有多余空格"。这三个细节，第一个影响程序结构，第二个影响公式和取模，第三个影响提交后是AC还是Presentation Error。

1.2 输入输出边界比算法本身更致命

上机实践题和平时写练习代码最大的区别在于，评测系统只认输出，不认过程。你逻辑再漂亮，格式错一个字符就是零分。我整理了一下这道题常见的边界场景，建议写代码之前先想清楚：

• n等于1时，程序能不能直接输出这个人的编号，不进入删除循环。
• m等于1时，出圈顺序就是1到n，但链表删除时会涉及前驱节点指针，处理不当就段错误。
• m远大于n时，比如n等于5、m等于100，报数会绕很多圈，模拟代码如果直接数到100，效率在数据量大时会变差，需要取模优化。
• 多组输入时，链表创建的节点要释放干净，避免内存泄漏。

这些边界不提前列出来，在本地测试时很难发现，因为人手工测试通常只会输入正常的n和m。可评测系统不一样，它会在后台塞一大堆极端数据。我自己做上机题的习惯是，读完题先写一版"测试用例清单"，至少包含：最小规模、最大规模、单组数据、多组数据、m等于1、m大于n、m和n相等。有了这个清单，代码写完直接按清单跑一遍，大部分低级错误在提交之前就能拦住。

1.3 从题目描述抽象出数据结构

约瑟夫环的抽象过程其实很有意思。人围成一圈，本质是一个循环序列；出圈操作，本质是从序列里删除一个元素，然后从下一个位置继续计数。这里有两个数据结构选择方向：

• 如果删除是核心操作，链表在理论上是最高效的，因为删除节点只需要改指针，时间复杂度O(1)。
• 但实际代码里，数组的连续内存访问对CPU缓存更友好，在n比较小的时候，数组实现的常数往往比链表还小。

所以不要一上来就"围成一圈等于循环链表"。你需要先评估n的取值范围。如果n不超过1万，数组模拟完全够用；如果n到10万、100万级别，链表模拟的时间会明显上升；如果题目只是问最后幸存者，那直接走数学路线。数据结构选型永远跟着数据规模走，而不是跟着题目描述走。

我见过太多人在链表和数组之间反复横跳，最后代码还没写对。上机的原则很简单：先在草稿纸上把数据规模、算法复杂度、代码难度这三者比较一遍，再动手。

2. 循环链表模拟：最贴合直觉，但指针坑最多

2.1 为什么教科书都选循环链表

在数据结构的教材里，约瑟夫环几乎必配循环链表。原因是这个数据结构跟题目描述是"直译"的：几个人围成一圈，链表尾节点指向头节点；出圈就是删除节点；从下一个继续，就是从删除节点的后继继续。对学生来说，理解起来几乎没有门槛。

但直译不代表好写。循环链表最烦的地方在于，删除一个节点必须知道它的前驱节点，而单链表找前驱需要从头遍历。网上很多版本是用"双指针"同时在链表上移动，一个指向当前节点，一个指向前驱，这本身没问题，可一旦遇到m等于1这种特殊情况，pre指针还没初始化就直接解引用，程序就炸了。我调试学弟代码的时候，第一个崩溃点就出现在这里。

2.2 完整实现与删除逻辑

下面这份代码是我调试后整理的版本，思路是：创建循环链表后，用一个tail指针指向尾节点，让pre初始指向tail，cur初始指向head。这样pre天然就是cur的前驱，不管m等于几都不会出现前驱为空的情况。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node* createCircle(int n) { Node *head = NULL, *tail = NULL; for (int i = 1; i <= n; i++) { Node *p = (Node*)malloc(sizeof(Node)); p->data = i; p->next = NULL; if (head == NULL) { head = p; } else { tail->next = p; } tail = p; } tail->next = head; return head; } void josephusList(int n, int m) { Node *head = createCircle(n); Node *pre = head; while (pre->next != head) { pre = pre->next; // 让 pre 指向尾节点 } Node *cur = head; while (cur->next != cur) { for (int i = 1; i < m; i++) { pre = cur; cur = cur->next; } printf("%d ", cur->data); pre->next = cur->next; Node *tmp = cur; cur = cur->next; free(tmp); } printf("%d\n", cur->data); free(cur); } int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { josephusList(n, m); } return 0; }

这段代码的关键细节有两个。第一个是pre的初始化，不能是NULL，必须指向cur的前驱，也就是链表尾节点。第二个是删除时的顺序：先把pre->next指向cur->next，把cur从链表里摘掉，然后让cur指向下一个节点，最后再free(tmp)，这样cur在逻辑上已经移动到出圈节点的下一个位置，符合"从下一个人重新报数"的规则。

2.3 实测结果和时间复杂度账

用n=5、m=3测试，输出是3 1 5 2 4，和手算结果一致；再用n=10、m=3测试，输出3 6 9 2 7 1 8 5 10 4，也没问题。看起来挺美，但时间复杂度其实不低。每次删除一个节点，都要在循环链表里走m步，总共要删除n-1个节点，所以整体复杂度是O(n*m)。如果n是1万、m是1万，就需要执行1亿次指针移动，在OJ上很可能超时。

这个问题在学弟第一次提交时立刻暴露了。他用的数据范围是n不超过10万、m不超过10万，链表版跑了大概几秒钟，评测系统直接判TLE。这不是代码写错，是算法选型错了。遇到这种数据规模，用链表模拟本质是拿一个O(n*m)的算法去挑战大数据，时间必然扛不住。

3. 数组标记法：上机时更快写完的方案

3.1 用状态数组模拟报数过程

链表会超时，一个自然的改进是用数组。数组版不需要动态分配内存，也不需要维护指针关系，只需要一个int数组标记每个人是否已经出圈。0表示在圈内，1表示已经出圈，然后用一个pos变量记录当前报数位置。

上机写这种题，数组版比链表版快得多，因为它的思维模型更贴近"报数"这个动作：人还在圈内，计数器就加一；计数器到达m时，当前位置的人出圈，改成标记1；然后pos从下一个人继续走，遇到已经是1的跳过。

#include <stdio.h> #include <string.h> int main() { int n, m; scanf("%d%d", &n, &m); int a[100005] = {0}; // 0 表示在圈内，1 表示已出圈 int count = n; int pos = 0; // 数组下标，代表编号 pos+1 while (count > 0) { int step = 0; while (step < m) { if (a[pos] == 0) { step++; if (step == m) break; } pos = (pos + 1) % n; } a[pos] = 1; printf("%d ", pos + 1); count--; if (count > 0) { while (a[pos] == 1) { pos = (pos + 1) % n; } } } printf("\n"); return 0; }

这个版本逻辑上最接近人的思考过程。注意pos从0开始，输出编号时加1。出圈一个人之后，count减1，然后pos要移动到下一个仍在圈内的位置，确保下一轮报数从正确的人开始。

3.2 链表与数组：上机时到底选哪个

我整理了一张对比表，直接列一下两种模拟方案在实践中的差异：

从我的经验看，上机实践题只要n在10万以内、m也不大，数组版是最稳的选择。它在足够多的测试数据下能顺利通过，且写起来快，万一出问题也容易定位。但如果你已经预估到n和m都是百万级别，那无论链表还是数组，O(n*m)的复杂度都兜不住，这时候必须换数学方案。

3.3 数组版的一个隐蔽效率问题

数组版虽然代码简单，但有个细节容易被忽略：当大量人已经出圈后，pos每走一步都要判断当前位置是否已经出圈，如果出圈人数多，这一步可能连续跳过很多位置。极端情况下，比如最后只剩一个人，而这个人前面全是出圈标记，程序就要绕一整圈才能找到他。这个额外开销累加起来，最坏情况下仍然接近O(n*m)。

所以数组版并不是银弹。它适合的是"数据规模中等、需要完整输出出圈顺序"的题目，不能指望它通吃所有测试点。我在第5节调试实录里会专门提到一个因为取模和跳过逻辑写错导致的死循环，就是数组版这个"跳过已出圈位置"环节出的问题。

4. 递推公式：只求幸存者的O(n)解法

4.1 为什么要把模拟扔掉

有些约瑟夫环的题只问一个东西：最后剩下的人是谁。比如"求幸存者的编号"，输入n和m，输出最后留下的人。遇到这种变体，模拟就完全是一种浪费了，因为模拟过程中输出了大量中间状态，而这些状态题目根本不需要。

这道2.3.4题目虽然要求输出完整出圈顺序，但很多上机题是从它改编的，改法就是去掉"输出顺序"这一步。我建议把递推解法也彻底吃透，因为同样的知识点换个问法就变一道新题。

数学解法的核心是递推关系。把问题看成n个人从0到n-1编号，m为报数上限。定义一个函数f(n, m)表示n个人时最后幸存者的编号（0-based），关键就是找到f(n, m)和f(n-1, m)之间的关系。

4.2 递推关系的完整推导

先看第一轮。n个人编号0到n-1，从0开始报数，报到m-1的人出圈，也就是编号为(m-1) % n的人被删除。这个编号为什么取模？因为m可能比n大，报数过程中会绕圈，第一轮出圈的编号就是m-1对n取余。

删除这个人之后，剩下n-1个人，他们重新从出圈者的下一个人开始报数。现在做一次重新编号：把出圈者后面的那个人记为新的0号，那么新旧编号之间有一个固定映射关系：

• 旧编号 = （新编号 + m） % n

这个映射可以从一个简单例子里验证。假设n=5、m=3，第一轮出圈的是编号2。出圈后剩下的4个人按顺序是3、4、0、1，重新编号成0、1、2、3。旧编号3对应新编号0，而(0+3)%5=3；旧编号0对应新编号2，而(2+3)%5=0。恰好吻合。

所以n个人时的幸存者，就是n-1个人时的幸存者先映射回原编号。递推式写出来就是：

• f(1, m) = 0
• f(i, m) = (f(i-1, m) + m) % i

这里的i从2循环到n，变量名写小写i更容易理解，因为取模的模数也在变化：当人数是i时，编号范围是0到i-1，所以取模i。

4.3 迭代实现与编号陷阱

有了递推式，代码只需要几行：

#include <stdio.h> int main() { long long n, m; scanf("%lld%lld", &n, &m); long long ans = 0; // 1个人时的幸存者，0-based for (long long i = 2; i <= n; i++) { ans = (ans + m) % i; } printf("%lld\n", ans + 1); // 转回1-based return 0; }

有人会问，为什么用long long？因为题目如果给到n和m都是10的9次方这个量级，ans加上m之后可能超过int的2的31次方范围，虽然取模之后会变小，但中间加法的瞬间会溢出。这种边界题折磨人的地方就在这，你明明知道公式是对的，就是因为一个int溢出，答案全错。

输出的时候要特别小心：公式推导用的是0-based编号，但题目输入输出通常用1-based编号。所以最后输出ans+1。这个"+1"是上机题的高频失分点，测试样例可能恰好不暴露问题，但一旦n和m的取值不同，少了这1位就会导致整个结果偏移。

4.4 为什么递推公式不能直接输出完整出圈顺序

这道题目要求输出完整顺序，递推公式不能直接做到。原因很简单：递推过程中我们只保留了"幸存者编号"这个信息，每一轮删了谁、删的顺序是什么，被压缩掉了。如果想用数学方案输出完整顺序，需要用树状数组或线段树维护"当前圈内第k个未出圈的人"这样的信息，每次找第m个人，然后从数据结构里删除，复杂度是O(n log n)。这个方案代码量比数组模拟大不少，上机考试时不建议冒险。

所以完整的问题解决方案应该是分层的：

• n很小，m很小：直接用数组模拟，代码短，容易调。
• n很大，m也大，但只问幸存者：用递推公式，O(n)。
• n很大，且要求完整出圈顺序：数组模拟会超时，需要线段树或树状数组。

先把题目要求搞清楚，再决定用哪一层，这才是上机实践的真正意义。

5. 完整调试实录：四个让我卡住的bug

5.1 指针漂移导致死循环

学弟第一次用链表写，本地跑n=5、m=3是对的，但跑n=10、m=3的时候就卡死。我帮他把循环体里加了两行printf，打印pre->data和cur->data，发现删除完第三个节点后，pre和cur的关系突然变得错乱，cur->next又指回了一个已经被free的节点。

原因出在删除语句的顺序上。他原本的代码是：

cur = cur->next; pre->next = cur->next;

这两句顺序一颠倒，pre->next指向的已经不是原来的cur->next，而是cur移动后的next，等于跳过了下一个有效节点。更危险的是，如果此时cur刚好是pre的后继，free之后pre还保留着指向已释放内存的悬空指针，下一次访问就直接段错误。

修复方式就是我在第2节写的顺序：先摘节点，再移动cur，最后释放。改成：

pre->next = cur->next; Node *tmp = cur; cur = cur->next; free(tmp);

这个bug的教训是：链表删除操作不要凭感觉写，一定要先理清"谁还被需要、谁已经可以被释放"。

5.2 m等于1时的段错误

第二个bug隐藏得更深。m等于1时，每次都是当前的人直接出圈，不需要走任何step。我最初看到的链表代码里，pre初始化为NULL，然后让pre跟着cur走m-1步。m等于1时，循环一次都不执行，pre还是NULL，删cur的时候写pre->next = cur->next，就相当于往NULL地址写数据，程序当场崩溃。

修复的思路是：永远不要让pre处于"未知"状态。我在最终版本里让pre初始指向尾节点，也就是head的前驱，这样就保证了不管m等于几，pre都一定存在且是cur的前驱。

这个bug也提醒我：上机测试用例里一定要包含m等于1这种极端输入。它不是刁难，而是考察你有没有真的理解数据结构的前驱后继关系。

5.3 数组版跳过逻辑引发的死循环

写完数组版后，我在n=10、m=3的时候跑得好好的，但自己加了一个n=5、m=100的用例，程序直接卡死。排查后发现问题在"跳过已出圈位置"的while循环：

while (a[pos] == 1) { pos = (pos + 1) % n; }

这个循环如果没有终止条件，理论上会在所有位置都是1的时候无限循环。正常情况下count>0保证了至少有一个位置是0，但如果count等于0之后再进入这个循环，就会死循环。我的代码里用if(count>0)做了保护，但学弟版本里没做，他在count减到0后仍然执行了这段跳过逻辑，程序就卡死了。

修复方式有两个：一是在外层while循环里先判断count是否大于0；二是保证出圈时，如果这是最后一个人，直接结束，不再执行任何跳过逻辑。这也是一个典型的边界条件问题：你设计的"跳过"逻辑要依赖"圈里还有人"，而"圈里还有人"这个条件在最后一个人出圈后会变成假。

5.4 行末空格引发的Presentation Error

这个bug跟算法无关，纯粹是输出格式。题目要求输出空格分隔的序列，行末不能有多余空格。我的第一个版本在每次printf编号后都带了一个空格，提交后判了Presentation Error，所有输出都对，但格式就是不给过。

修复很简单：把输出结果存到数组里，最后统一输出，判断当前是不是最后一个元素；或者每次输出前判断计数器，如果是第一个输出的编号就不打空格，之后每个编号前打一个空格。后者更省内存：

if (first) { printf("%d", pos + 1); first = 0; } else { printf(" %d", pos + 1); }

上机实战里，Presentation Error看起来是小事，但它会浪费你宝贵的提交机会。我后来养成一个习惯：写完代码先检查所有printf，凡是涉及循环输出的，都问自己一句"行尾到底允不允许多一个空格"。

6. 做完这道题，我改掉了三个上机习惯

这道2.3.4做完之后，我自己上机的操作顺序变了不少。以前我拿到题的第一反应是"这个数据结构我熟，开写"，现在我会先做三件事。

第一件事，把题目的数据范围抄到草稿纸上。数据范围不是给数学题准备的，是给算法选型用的。看到n不超过1000，那就大胆用数组模拟；看到n是10的7次方，直接考虑递推或更高级的数据结构。范围稍微一变，整个方案就要跟着变，这是最需要提前判断的。

第二件事，写代码之前先列边界测试用例。我不是列给自己看的，是列给代码看的。n等于1、m等于1、m大于n、n等于m，这些用例在代码写完之后一分钟不到就能全部跑完，但能拦住一半以上的低级错误。每次上机题卡住，我都先回去看边界用例跑没跑，而不是盯着主逻辑改来改去。

第三件事，调试的时候多用printf输出关键变量。很多同学怕printf污染代码，其实上机环境里它就是最趁手的调试工具。链表指针不确定，打印pre和cur的data；数组下标不确定，打印pos和step；递推结果不对，打印每一轮的ans。打印一遍，问题基本就现身了。

最后说一个和算法无关但很重要的心得：上机实践题不像竞赛题那样追求一上来就写出最优解，它更看重你解决问题的完整度。先用最直白的方式写一个能跑通小数据的版本，再分析复杂度瓶颈，再针对瓶颈优化，这个流程比第一次就憋大招稳妥得多。2.3.4这道题，从链表到数组再到递推，恰好就是一条完整的上机优化路径。踩过这些坑之后，我反而觉得它是那道最值得做的入门题。