约瑟夫环（Josephus Problem）这个题目，我每次看到都有一种“明明很简单，写出来总是绕”的感觉。如果你也正在数据结构课上学到循环链表，或者准备面试时刷到这道经典模拟题，这篇笔记应该能让你少走很多弯路。文章会围绕C语言的三种实现思路展开：循环链表直接模拟、数组标志位模拟，以及一个很多人只知道结论却不会推导的数学递推法。我不光给代码，还会把每一步为什么这么写、指针怎么走、边界条件在哪，全部拆开讲清楚。
1. 约瑟夫问题的数学模型：先搞清楚题目在问什么
1.1 规则描述与两种常见变体
约瑟夫问题的背景有好几个版本，但核心规则是一致的：有n个人围成一圈，从某个位置开始报数，每数到第k个人，这个人就出局，然后由下一个人重新从1开始报数，如此循环，直到圈里只剩最后一个人。我们的任务是求这个最后幸存者的编号，或者求出完整的出局顺序。
这里有一个很多初学者一开始不太注意的分叉点：题目可能是让你求最终幸存者，也可能让你按顺序输出全部出局的人。这两种问法直接决定了你用哪种算法。
- 如果只问幸存者，可以用数学递推做到O(n)复杂度，代码短到惊人。
- 如果要输出每次出局的人，那本质上必须“模拟”整个淘汰过程，递推公式帮不上忙，至少不能直接帮忙。
另外，编号从0开始还是从1开始，也会直接影响递推公式的写法。C语言习惯从0开始计数，很多教材也会用0到n-1来建模，但作业和考试题经常用1到n来编号。这个细节后面我会专门讲，因为不少代码“死”就死在这个偏移量上。
1.2 参数定义与边界条件
为了后面代码不混乱，先把参数统一一下：
| 参数 | 含义 | 常见范围 |
|---|---|---|
| n | 总人数 | n ≥ 1 |
| k | 报数阈值，数到k的人出局 | k ≥ 1 |
| start | 从哪个人开始报数 | 0到n-1，或1到n，随题目而定 |
| survivor | 最终幸存者编号 | 1到n（或0到n-1） |
注意k的范围。如果k=1，那从谁开始就谁出局，问题退化成“从左到右挨个出局”，这个特例能帮你验证代码是否正确。如果k比n大很多，比如n=7而k=1000000，那是继续老老实实模拟，还是可以直接取模？很多人的第一反应是k对n取模，但要注意每出局一个人，圈里人数就变化一次，所以取模的模数也在变化，不能从头到尾只取一次。这个问题到第四节递推时会有更清晰的答案。
1.3 为什么这题总是出现在链表章节
约瑟夫环之所以在数据结构课上有如此稳固的地位，不是因为它难，而是因为它把两个核心知识点天然地串在了一起：环形结构和节点删除。
数组可以用取模模拟环，但数组删除元素要搬移数据，复杂度高；链表不需要搬移，却要求你对指针操作足够熟练，尤其要理解“删除节点时，必须让前一个节点的next绕过当前节点”这件事。约瑟夫环恰好逼着你把这个逻辑写熟。
面试里经常用这道题考察候选人的基本功，也是同一个原因：代码量不大，但很能反映出一个人是否真正理解指针语义，而不是背模板。下面三种做法，我建议都亲手写一遍，互相印证，比你只看不写记忆深刻得多。
2. 单向循环链表的直接模拟：把游戏规则翻译成C代码
2.1 节点结构体与环形链表的构建
链表解法的思路非常朴素：用结构体表示一个人，data存编号，next存下一人的地址，然后把最后一个节点的next指回头节点，这样就构成了一个圈。
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node;构建n个节点的环形链表时，有一个小细节：要不要设置头节点？我的建议是不要，直接用第一个数据节点作为环形链表的入口。如果不带头节点，循环条件可以写成“当前节点的next不指向自己”来判断是否只剩一个节点，逻辑非常清晰；如果带头节点，链表里凭空多了一个不参与报数的节点，每轮删除都要费劲地跳过它，纯属给自己添堵。
Node* create_circle(int n) { if (n <= 0) return NULL; Node *head = NULL; Node *tail = NULL; for (int i = 1; i <= n; i++) { Node *new_node = (Node*)malloc(sizeof(Node)); new_node->data = i; // 编号从1开始 new_node->next = NULL; if (head == NULL) { head = new_node; } else { tail->next = new_node; } tail = new_node; } tail->next = head; // 首尾相接，形成环 return head; }这段代码里，head始终指向第一个人，tail一路跟着新节点往后走。最后一步tail->next = head是整个环形链表的关键，少了这一步，后面遍历时会直接在空指针上崩溃。
2.2 报数与删除节点的循环逻辑
构建好环形链表后，进入核心的模拟过程。我们需要两个指针：一个cur指向当前要处理的人，另一个prev永远指向cur的前一个人。删除cur所指向的节点时，只需把prev->next指向cur->next，然后free掉cur。
这里有一个重要的初始动作：很多人在构建完链表后直接让cur = head，但那样prev就不知道指谁了。正确做法是先让prev从头节点开始，一直走到最后一个节点，也就是让prev = head的前驱，这样一开始cur = head时，prev确实就是cur的前一个节点。
int josephus_circle(Node **head_ref, int k) { if (*head_ref == NULL || k <= 0) return -1; Node *cur = *head_ref; Node *prev = *head_ref; // 让prev成为cur的前驱，即指向链表最后一个节点 while (prev->next != *head_ref) { prev = prev->next; } // 游戏开始，直到只剩一个节点 while (cur->next != cur) { // 报数到第k个人：需要向前走k-1步，因为cur本身就数“1” for (int i = 1; i < k; i++) { prev = cur; cur = cur->next; } // 此时cur就是要出局的人 Node *to_delete = cur; printf("%d ", to_delete->data); // 摘除cur节点 prev->next = cur->next; cur = prev->next; free(to_delete); } // 最后剩下的一个节点 int survivor = cur->data; printf("\n幸存者：%d\n", survivor); free(cur); *head_ref = NULL; return survivor; }这里的核心逻辑在那个for循环里。很多人会问：为什么报数到k只要移动k-1次？因为cur已经站在“第一个人”的位置上，从1数到k共k个数，所以相对位移是k-1。如果你把这个数成k，每次都会多走一格，结果会整体错位，而且错位的误差会累积，最终结果完全不对。
2.3 链表法的边界条件与示例验证
拿n=7，k=3来验证一下。构建链表后编号为1-2-3-4-5-6-7，首尾相连。
- 第一轮：cur初始指向1，报数1、2、3，3出局。链表变为1-2-4-5-6-7，下一步从4开始。
- 第二轮：4、5、6依次报数，6出局。链表变为1-2-4-5-7，下一步从7开始。
- 第三轮：7、1、2，2出局。链表变为1-4-5-7，下一步从4开始。
- 第四轮：4、5、7，7出局。链表变为1-4-5，下一步从1开始。
- 第五轮：1、4、5，5出局。链表变为1-4，下一步从1开始。
- 第六轮：1、4、1，1出局。链表只剩下4。
所以n=7、k=3的幸存者是4号。你可以自己顺一遍代码，看是不是正好输出：3 6 2 7 5 1，最后幸存者4。这个手动验证的过程我强烈建议你做一遍，它能帮你在不看调试器的情况下，迅速发现自己写的循环到底错在哪一步。
一个容易被忽略的边界条件是：当链表只剩一个节点时，cur->next == cur，循环条件直接不满足，所以不会进入删除逻辑。最后那个幸存者节点的next指向自身，free之前不需要额外处理它的后继，直接free即可。
3. 数组模拟环形结构：不写链表，也能解约瑟夫环
3.1 下标取模法：用算术模拟环的循环
链表法虽然直观，但很多学校的数据结构作业要求“只能用数组”实现。这时就需要用下标取模来模拟环形的回绕效果：当i走到n-1时，i+1模n的结果是0，自然就回到了数组开头。
数组法有两种删除策略：
- 覆盖法：每出局一个人，就把后面所有元素往前搬一位，数组长度减一。这种方法的时间代价主要在数据搬移，最坏情况下每轮都是O(n)，总体复杂度高。
- 标志位法：数组值表示该位置是否出局，出局置1，仍在局内保持0。报数时跳过已出局位置。这种方法不搬数据，但需要在报数时额外判断并跳过“空位”。
实际写下来，标志位法更接近链表的模拟逻辑，只是在“找下一个仍在圈内的人”时多了一个判空步骤。下面给出标志位法的完整实现。
3.2 标志位数组的完整实现
int josephus_array(int n, int k) { if (n <= 0 || k <= 0) return -1; // 0表示在圈内，1表示已出局 int *out = (int*)calloc(n, sizeof(int)); int remain = n; // 仍在圈内的人数 int idx = 0; // 当前下标，从第一个人开始 printf("出列顺序："); while (remain > 1) { int step = 0; // 找到本轮要出局的人 while (step < k) { if (out[idx] == 0) { step++; if (step == k) break; } idx = (idx + 1) % n; } // idx指向出局者 out[idx] = 1; printf("%d ", idx + 1); // 因为用0编号，输出时+1 remain--; // 如果还有人没有被淘汰，移到下一个在圈内的人 if (remain > 0) { do { idx = (idx + 1) % n; } while (out[idx] == 1); } } // 找出唯一没出局的人 for (int i = 0; i < n; i++) { if (out[i] == 0) { printf("\n幸存者：%d\n", i + 1); free(out); return i + 1; } } free(out); return -1; }这个代码里最容易出错的是那个内层while循环。很多人会写不判断out[idx]就直接数step，结果把已经出局的人又数了一遍，最后一圈转下来删了不存在的幸存者，或者陷入死循环。我在初学时就在这里翻过车：当时k=3，n=5，程序跑起来后怎么都删不完人，打印出来的出列顺序还带着重复编号，debug了很久才发现是没跳过已出局的位置。
另外注意出局后移动idx的方式。出局者下标是idx，那么下一个从idx+1开始找，但idx+1可能也已经出局了，所以要用一个do-while循环，不断往前找，直到找到out为0的下标。这个“寻找下一个活人”的过程，正是链表法中cur = cur->next的数组版本。
3.3 为什么数组法的实际速度反而可能更快
如果光看时间复杂度，链表法和标志位数组法都是O(n*k)，但真实运行时的差异不小。链表法每走一步都要通过指针访问分散在堆内存里的节点，触发的缓存缺页比连续数组多得多；数组访问就是连续内存的下标访问，即使要跳过已出局位置，整体还是比链表快。我在本机跑n=100000、k=100时，链表法耗时大约是数组法的3到5倍，差别非常明显。
但数组法也有它的尴尬之处：当k很大而n也很大时，判断“跳过已出局的人”会频繁触发，尤其是游戏后期存活者稀疏的时候，每个报数动作都可能要检查大片连续出局位置。比如n=100000，到最后一轮，内层while可能要扫过接近n个位置才能找到一个活人。这时候数组法的实际表现也会很难看。
4. 数学递推的O(n)解法：约瑟夫环的底层规律
4.1 从递归关系中看见规模的缩减
链表和数组都是模拟视角，它们把问题当作“游戏过程”来执行。数学递推的出发点是另一个角度：当一个人出局后，剩余的人重新编号，问题规模就缩减了1。
具体来说，设f(n, k)表示n个人从0开始编号、报数到k出局时最终幸存者的编号。n=1时，f(1, k)=0，因为只有编号0一个人，他当然幸存。
问题在于n>1时怎么从f(n-1, k)推出f(n, k)。考虑n个人时第一轮出局的是编号(k-1) mod n的人，出局后剩下n-1个人，并且下一个报数的人编号是k mod n。如果我们把“下一个报数的人”重新编号为0，把新0后面的人重新编号为1、2……那么剩下的这n-1个人就构成了一个规模为n-1的全新约瑟夫环，它的幸存者在新编号体系下的值是f(n-1, k)。
关键一步是“新旧编号的换算”：新编号为x的人，在原编号体系中是(x + k) mod n。因为重新编号时，原编号k mod n变成了新编号0，所以原编号 = 新编号 + k，再对n取模。于是：
f(n, k) = (f(n-1, k) + k) mod n
边界条件是f(1, k) = 0。这就是整个递推的全部。
4.2 用一个具体例子验证递推公式
还是用n=7，k=3，编号从0到6来验证：
- f(1)=0
- f(2)=(0+3)%2=1
- f(3)=(1+3)%3=1
- f(4)=(1+3)%4=0
- f(5)=(0+3)%5=3
- f(6)=(3+3)%6=0
- f(7)=(0+3)%7=3
最终结果是3，换算成从1开始的编号就是4号，和前面链表法手动模拟得到的幸存者完全一致。如果你在面试里碰到了这道题，可以先快速在纸上推一遍这个递推，再用小规模数据验证，心里就会非常有底。
4.3 递归版和迭代版的C代码实现
递推关系一旦建立，代码极其简洁：
// 递归版：编号从0开始 int josephus_recursive(int n, int k) { if (n == 1) return 0; return (josephus_recursive(n - 1, k) + k) % n; } // 迭代版：消除递归栈开销 int josephus_iterative(int n, int k) { int survivor = 0; // f(1) = 0 for (int i = 2; i <= n; i++) { survivor = (survivor + k) % i; } return survivor; }注意递归版的返回值是基于0编号的。如果题目要求从1开始编号，在调用处加个1即可。迭代版的时间复杂度是O(n)，空间复杂度是O(1)，这是三种方案里最优的。
但这里有一个特别容易犯的错误：有人会把公式里的模数写成固定的n。这不对。当规模从i-1缩小到i-1再变到i时，模数必须跟随当前总人数变化。迭代版里每一步的模数是i，正是当前的“总人数”，不是最初的n。这也是为什么不能写成(survivor + k) % n——那样结果会在某些数据上完全错位。
4.4 递推法的局限：它算不出出列顺序
既然递推这么好用，是不是作业里的约瑟夫环都该用它？不是。递推公式只能求幸存者的编号，没有办法回溯出每一轮出局的人是谁。你想想，递推过程一直在压缩问题规模，每一步都丢失了具体的编号映射信息，最后只留一个终点结果。所以如果题目要求“按顺序输出所有出局者的编号”，求解器就必须回到模拟路线。
面试时有个策略值得参考：如果面试官问约瑟夫环，可以先问清楚“只求幸存者还是求完整出列顺序”。如果只说求最后一个活着的人，递推法会是一个让人眼前一亮的答案；如果面试官追问出列顺序，再切到链表或数组模拟实现，还能展示你思路的全面性。
5. 三种方案的时间复杂度对比与选型策略
5.1 复杂度总览
把三种方案的复杂度放在一起看：
| 方案 | 时间复杂度 | 空间复杂度 | 能输出完整出列顺序 | 实现难度 |
|---|---|---|---|---|
| 循环链表模拟 | O(n*k) | O(n) | 能 | 中 |
| 数组标志位模拟 | O(n*k) | O(n) | 能 | 低 |
| 数学递推 | O(n) | O(1)（迭代版） | 不能 | 低 |
表格只能说明大O，实际使用中还有几个微妙点。链表模拟虽然复杂度也是O(n*k)，但每轮的k步是“每次跳过一个节点”，而数组标志位法每轮的k步要额外跳过已出局位置，所以数组法的实际核心操作次数往往大于链表法。不过数组访问的常量因子很小，在moderate规模下依然可能反超链表。真要比较，建议在自己机器上跑几组不同n、k的数据，观察耗时再下结论。
5.2 面对不同题目场景，应该选哪种实现
我的建议是按下述规则选型：
- 题目明确要求循环链表实现：直接选链表模拟，毕竟练习目的是理解指针操作。
- 题目只求幸存者、n可以非常大（比如n=10^7，k任意）：选递推，O(n)能撑住，链表和数组大概率超时。
- 题目要求输出完整的出列序列，n中等规模（比如n<=10^5）：选数组标志位法，代码简单，运行快。
- 面试场景，只求幸存者：先给递推，如果面试官问“还能怎么做”，再补充链表模拟思路。
5.3 n和k都很大的时候，模拟法会暴露真正的问题
当k远大于n时，模拟法的性能会很难看。比如n=100000，k=1000000，链表法每个幸存者都要数百万次指针跳转，淘汰完所有人可能要跑上亿次迭代，几分钟都不一定能出结果。而递推法只循环n次，每次做一次加法、一次取模，瞬间完成。
如果你必须用模拟法处理大k，有个优化思想暗含在取模运算里：某一轮圈里还有m个人时，从当前位置走到出局者需要走的步数，其实是(k-1) mod m。也就是说，当k很大时，可以先用取模把步数压缩到小于m，再让指针或下标前进。注意这里的模数m是当前圈内人数，不是初始n，而且每一步淘汰后m都会变化，所以不能只算一次。你可以把取模后的步数替换链表for循环中的k-1步，这样能显著减少跳跃次数。这个是扩展优化，作业中用不用都行，理解了原理会有帮助。
6. 代码细节上的那些坑：每个都曾经让我debug到怀疑人生
6.1 指针悬空与重复释放
链表法常见的崩溃来源有两个：一是free了节点之后还在用这个节点指针，二是删除最后一个节点后没有把外部入口指针置空。之前那个josephus_circle函数，我特意设计了Node **head_ref参数，并且最后把*head_ref置为NULL，就是为了防止调用方在函数返回后还继续访问已被释放的链表。
实际写代码时，我建议在每个free之后立刻把对应指针赋为NULL，这是个成本极低但收益极高的习惯。虽然把空指针写上有点繁琐，但当你误用了已经释放的指针时，至少不会立刻访问到野地址，程序会在相对可控的位置报错。
6.2 编号从0还是从1：一处偏移，全盘皆错
递推公式天然使用0编号，但很多题目和人习惯使用1编号。如果你在递归代码中用了n=7，手动验证出来结果3，因为题目问“编号几幸存”，你把3直接写成答案，而正确答案是4号。这类错误最坑的是，代码本身一点没错，只是输出时少加了1。
我的处理办法是：在一个独立函数里始终用0编号完成核心逻辑，只在最外层封装时做编号转换。这样递推核心不会因为外界编号方式改变而修改。链表和数组方案里，构建节点时数据域可以直接存1到n，输出也不用转换，但要注意数组下标和编号之间的对应关系：out数组的下标0对应编号1。
6.3 报数步数与取模的边界
链表法的for循环里，i从1循环到k-1，有人会写成i<=k，导致每轮都多走一个节点。这个问题怎么排查？我建议在for循环里临时打印每一步经过的节点编号，和手动模拟对比。比如n=7、k=3，第一轮应该是cur路径1→2→3，3出局。如果你发现路径变成1→2→3→4，那不用犹豫，就是步数多写了。
数组标志位法对应的坑，是出局之后寻找“下一个活人”时忘了考虑边界。如果idx已经走到最后一个位置，不要害怕取模，用(idx + 1) % n回到开头。很多人会在这个位置写一个if判断然后直接把idx设为0，虽然效果一样，但一旦将来代码扩展成不从0开始编号，这种if写法就容易引入新错误。直接用取模表达环形回绕，语义也更清晰。
6.4 调试技巧：让程序把“决策过程”讲给你听
C语言没有方便的调试器时，最有效的办法就是打印。我的建议是在链表的删除动作前打印当前处理的编号，在数组法中打印每轮选中的下标，同时打印剩余人数。这样就算结果错了，也能定位到具体某一轮开始出错，而不是对着一个最终错误答案瞎猜。
如果你在Linux环境，强烈推荐用valgrind跑一遍链表版本。你写链表如果忘了free任何节点，valgrind会明确报告“definitely lost”的内存字节数。有一次我就是靠它发现在某个分支提前return，漏掉了后面两个节点的释放，修掉后程序才在长时间循环测试里真正稳定。
6.5 从这道题里真正应该带走的东西
学约瑟夫环时，我一度沉迷于背那个递推公式，觉得自己“秒杀”了这道经典题。后来写了几次模拟代码，又回头推公式，才意识到这道题最有价值的不是公式本身，而是从模拟到抽象的观察过程。你先是动手模拟了游戏，看到每一轮的规律，然后抽象出一个规模递减的子问题，最终才导出递推关系。这个“先实现，再抽象，再优化”的路径，几乎适用于所有算法学习中遇到的经典问题。
如果让我给一个最具体的建议：写链表解法之前，先在纸上画一个只有5个节点的环形图，手动走两轮，把cur和prev的跳转路径标出来。你亲手画过之后，再写起来会比直接敲键盘顺畅得多。
最后再分享一个小技巧：你可以在链表模拟的delete分支里顺手统计一下总共free了多少个节点，应该等于n-1；如果不对，说明你的循环退出条件有偏差。这个方法我每次写完都会验证一遍，已经帮我在好几道类似的环形链表题目里抓出了隐藏bug。
