约瑟夫环Josephus Problem这个题目我每次看到都有一种“明明很简单写出来总是绕”的感觉。如果你也正在数据结构课上学到循环链表或者准备面试时刷到这道经典模拟题这篇笔记应该能让你少走很多弯路。文章会围绕C语言的三种实现思路展开循环链表直接模拟、数组标志位模拟以及一个很多人只知道结论却不会推导的数学递推法。我不光给代码还会把每一步为什么这么写、指针怎么走、边界条件在哪全部拆开讲清楚。1. 约瑟夫问题的数学模型先搞清楚题目在问什么1.1 规则描述与两种常见变体约瑟夫问题的背景有好几个版本但核心规则是一致的有n个人围成一圈从某个位置开始报数每数到第k个人这个人就出局然后由下一个人重新从1开始报数如此循环直到圈里只剩最后一个人。我们的任务是求这个最后幸存者的编号或者求出完整的出局顺序。这里有一个很多初学者一开始不太注意的分叉点题目可能是让你求最终幸存者也可能让你按顺序输出全部出局的人。这两种问法直接决定了你用哪种算法。如果只问幸存者可以用数学递推做到O(n)复杂度代码短到惊人。如果要输出每次出局的人那本质上必须“模拟”整个淘汰过程递推公式帮不上忙至少不能直接帮忙。另外编号从0开始还是从1开始也会直接影响递推公式的写法。C语言习惯从0开始计数很多教材也会用0到n-1来建模但作业和考试题经常用1到n来编号。这个细节后面我会专门讲因为不少代码“死”就死在这个偏移量上。1.2 参数定义与边界条件为了后面代码不混乱先把参数统一一下参数含义常见范围n总人数n ≥ 1k报数阈值数到k的人出局k ≥ 1start从哪个人开始报数0到n-1或1到n随题目而定survivor最终幸存者编号1到n或0到n-1注意k的范围。如果k1那从谁开始就谁出局问题退化成“从左到右挨个出局”这个特例能帮你验证代码是否正确。如果k比n大很多比如n7而k1000000那是继续老老实实模拟还是可以直接取模很多人的第一反应是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 链表法的边界条件与示例验证拿n7k3来验证一下。构建链表后编号为1-2-3-4-5-6-7首尾相连。第一轮cur初始指向1报数1、2、33出局。链表变为1-2-4-5-6-7下一步从4开始。第二轮4、5、6依次报数6出局。链表变为1-2-4-5-7下一步从7开始。第三轮7、1、22出局。链表变为1-4-5-7下一步从4开始。第四轮4、5、77出局。链表变为1-4-5下一步从1开始。第五轮1、4、55出局。链表变为1-4下一步从1开始。第六轮1、4、11出局。链表只剩下4。所以n7、k3的幸存者是4号。你可以自己顺一遍代码看是不是正好输出3 6 2 7 5 1最后幸存者4。这个手动验证的过程我强烈建议你做一遍它能帮你在不看调试器的情况下迅速发现自己写的循环到底错在哪一步。一个容易被忽略的边界条件是当链表只剩一个节点时cur-next cur循环条件直接不满足所以不会进入删除逻辑。最后那个幸存者节点的next指向自身free之前不需要额外处理它的后继直接free即可。3. 数组模拟环形结构不写链表也能解约瑟夫环3.1 下标取模法用算术模拟环的循环链表法虽然直观但很多学校的数据结构作业要求“只能用数组”实现。这时就需要用下标取模来模拟环形的回绕效果当i走到n-1时i1模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结果把已经出局的人又数了一遍最后一圈转下来删了不存在的幸存者或者陷入死循环。我在初学时就在这里翻过车当时k3n5程序跑起来后怎么都删不完人打印出来的出列顺序还带着重复编号debug了很久才发现是没跳过已出局的位置。另外注意出局后移动idx的方式。出局者下标是idx那么下一个从idx1开始找但idx1可能也已经出局了所以要用一个do-while循环不断往前找直到找到out为0的下标。这个“寻找下一个活人”的过程正是链表法中cur cur-next的数组版本。3.3 为什么数组法的实际速度反而可能更快如果光看时间复杂度链表法和标志位数组法都是O(n*k)但真实运行时的差异不小。链表法每走一步都要通过指针访问分散在堆内存里的节点触发的缓存缺页比连续数组多得多数组访问就是连续内存的下标访问即使要跳过已出局位置整体还是比链表快。我在本机跑n100000、k100时链表法耗时大约是数组法的3到5倍差别非常明显。但数组法也有它的尴尬之处当k很大而n也很大时判断“跳过已出局的人”会频繁触发尤其是游戏后期存活者稀疏的时候每个报数动作都可能要检查大片连续出局位置。比如n100000到最后一轮内层while可能要扫过接近n个位置才能找到一个活人。这时候数组法的实际表现也会很难看。4. 数学递推的O(n)解法约瑟夫环的底层规律4.1 从递归关系中看见规模的缩减链表和数组都是模拟视角它们把问题当作“游戏过程”来执行。数学递推的出发点是另一个角度当一个人出局后剩余的人重新编号问题规模就缩减了1。具体来说设f(n, k)表示n个人从0开始编号、报数到k出局时最终幸存者的编号。n1时f(1, k)0因为只有编号0一个人他当然幸存。问题在于n1时怎么从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 用一个具体例子验证递推公式还是用n7k3编号从0到6来验证f(1)0f(2)(03)%21f(3)(13)%31f(4)(13)%40f(5)(03)%53f(6)(33)%60f(7)(03)%73最终结果是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可以非常大比如n10^7k任意选递推O(n)能撑住链表和数组大概率超时。题目要求输出完整的出列序列n中等规模比如n10^5选数组标志位法代码简单运行快。面试场景只求幸存者先给递推如果面试官问“还能怎么做”再补充链表模拟思路。5.3 n和k都很大的时候模拟法会暴露真正的问题当k远大于n时模拟法的性能会很难看。比如n100000k1000000链表法每个幸存者都要数百万次指针跳转淘汰完所有人可能要跑上亿次迭代几分钟都不一定能出结果。而递推法只循环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编号。如果你在递归代码中用了n7手动验证出来结果3因为题目问“编号几幸存”你把3直接写成答案而正确答案是4号。这类错误最坑的是代码本身一点没错只是输出时少加了1。我的处理办法是在一个独立函数里始终用0编号完成核心逻辑只在最外层封装时做编号转换。这样递推核心不会因为外界编号方式改变而修改。链表和数组方案里构建节点时数据域可以直接存1到n输出也不用转换但要注意数组下标和编号之间的对应关系out数组的下标0对应编号1。6.3 报数步数与取模的边界链表法的for循环里i从1循环到k-1有人会写成ik导致每轮都多走一个节点。这个问题怎么排查我建议在for循环里临时打印每一步经过的节点编号和手动模拟对比。比如n7、k3第一轮应该是cur路径1→2→33出局。如果你发现路径变成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。