约瑟夫环问题详解：从循环链表到数学递推的三种解法

数据结构课里有一道题几乎每个学 C 语言的人都绕不过去——约瑟夫环Josephus Problem。题面很短n 个人围成一圈从第 k 个人开始报数报到 m 的人出列下一个人重新从 1 报数直到剩下最后一个人求这个人的编号或者求完整的出列顺序。很多第一次接触的人看到这个题会觉得很简单但真正打开编译器写起来10 个里面有 6 个会卡在“删完节点之后指针怎么走”上。这篇文章我就把这道题从思路到代码完整拆一遍覆盖循环链表、数组模拟和数学递推三种解法还会把我在实际调试中踩过的坑一并列出。适合正在上数据结构课、准备期末或考研或者想补一补 C 语言基本功的读者。1. 约瑟夫环问题到底在问什么1.1 题目描述与一个经典示例先统一一下题目的标准说法n 个人围成一圈按顺时针方向编号 1 到 n。从编号为 k 的人开始报数注意第 k 个人本人报的是 1然后顺时针方向的下一个人报 2报到数字 m 的人出圈出圈后从他顺时针方向的下一个人开始重新从 1 报数继续执行相同规则。问最后剩下的那个人是谁或者要求输出完整的出列顺序。这个“第 k 个人报 1”的细节极其容易让人栽跟头。很多初学者会在代码里写成“先把指针移动到 k 的下一个位置再开始报 1”结果整个逻辑全部错位。我后面写实现时会反复强调这一点。拿 n5、k1、m2 来手推一遍作为后面验证代码的标准用例。初始圈为 1、2、3、4、5从 1 开始报数1 报 12 报 22 出列从 3 重新开始3 报 14 报 24 出列从 5 重新开始5 报 11 报 21 出列从 3 重新开始3 报 15 报 25 出列最后剩下 3。所以这个用例下完整的出列顺序是 2、4、1、5幸存者是 3。这个结论以后写代码时要能对得上。1.2 这道题真正考察的四个能力约瑟夫环不是一道“背模板”的题它把计算机专业基础课里的好几块知识点串在了一起。我重新梳理之后认为它主要考察四点。第一线性表的理解。题目里的“围成一圈”是一个典型的环形结构你可以用顺序存储数组表达也可以用链式存储循环链表表达两种表达方式决定了后续删除操作的成本完全不同。第二指针或下标的精准控制。链表方案要维护当前节点和前驱节点数组方案要处理下标越界和删除后的元素移动任何一个地方少移一步、多移一步都会导致结果错误。第三边界情况的防御意识。n1、m1、k1 这些极限输入不是刁难而是任何真实程序里都会出现的合法情况代码必须能正确处理而不是直接越界或者死循环。第四算法优化的意识。同样是解这道题链表模拟是 O(n*m)数组前移是 O(n^2)数学递推却是 O(n)这种同一问题下不同数量级的对比正是数据结构与算法这门课最想训练的东西。2. 三种解法选型为什么链表、数组、数学解都存在2.1 循环链表天然匹配“围成一圈”的结构第一次看到约瑟夫环的人直觉反应基本都是“这不就是个环形链表吗”。这个直觉是对的因为题目描述的“围成一圈、顺时针报数、出列后跳过”本质上就是循环链表的遍历加删除操作。用单向循环链表时每个节点存一个人的编号尾节点的 next 指向头节点整个结构天然形成闭环。链表方案最讨巧的地方在于删除节点只需要改几行指针时间复杂度是 O(1)而且不需要像数组那样把后面的元素批量搬移。不过这有个前提你手上得拿着被删节点的前驱节点。单向链表只有 next 指针删除某个节点时必须知道它前一个节点是谁否则断链后就没法把前驱接到后继上了。这就是为什么几乎所有教科书实现都会定义一个 prev 指针跟着 cur 一起走。我记得第一次写这个题的时候脑子里想的是“循环链表简单”结果手上写出来的指针乱成一团核心问题就出在我一开始根本没有维护 prev删除节点时才发现拿不到前驱。后来学乖了在循环里始终让 prev 是 cur 的前驱删除时执行prev-next cur-next然后再把 cur 指向prev-next作为下一轮报数起点逻辑就顺畅了。2.2 数组法不用指针也能实现但代价是什么不想碰指针的人会优先考虑数组。数组方案有两种常见写法第一种是“标记法”开一个 flag 数组记录每个位置是否已经出列然后不断循环扫描遇到未出列的人就报数报到 m 就把标记置为 1。这种写法思路最简单但每次找下一个未出列的人都要逐个检查标记实际上每一轮都要扫描很多无效位置常数因子比链表大不少。第二种是“前移法”让数组动态缩短每当有人出列就把后面所有元素往左移动一位同时用一个变量 len 记录当前环的有效长度。这样下一轮的报数起点天然落在被删位置因为原来的后一个元素已经补过来了。这个方案省去了指针和标记判断代码结构非常清晰但代价是每次删除都要移动大量元素整体复杂度上升到 O(n^2)。数组方案我建议初学阶段一定要写一遍不是为了效率而是为了理解“物理位置移动”和“逻辑报数位置”的关系。等你被 O(n^2) 折磨过一次回头再看链表和数学解就会明白为什么数据结构这门课要引入链表为什么有人费尽心机去推数学公式。2.3 数学递推法O(n) 求解最后一人的秘诀第三种解法不依赖任何存储结构只用一段极短的递推公式就能算出最后幸存者的编号。它的思路是反向思考先不看 n 个人的完整过程而是考虑“如果只有 1 个人幸存者是谁”再逐步反推回 n 个人的情况。公式长这样设 f(1)0对于 i 从 2 到 n有 f(i)(f(i-1)m) mod i。最后当编号从 1 开始、从第 k 个人开始报数时结果为 (f(n)k-1) mod n1。为什么 f(1)0因为如果只有 1 个人他的编号在当前编号体系里是 0幸存者当然是他。这个推导我放在第 5 章详细展开这里只需要知道数学解能做到 O(n) 时间和 O(1) 空间代价是你必须先理解清楚“编号重映射”的过程。三种解法没有绝对优劣。链表最直观数组最好写数学解最高效。实际做题或面试时优先把链表和数学解掌握数组作为保底方案。3. 从零手写循环链表实现完整代码与逐段拆解3.1 节点定义与环的构建链表的节点结构很简单一个整数 data 存编号一个 next 指针指向下一个节点。我用 typedef 定义 Node后续写起来会短一些。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node;创建环形链表的核心是先把节点按编号 1 到 n 串成普通单链表记录头节点 head 和尾节点 tail最后执行tail-next head让链表首尾相接。Node *createLoop(int n) { Node *head NULL, *tail NULL; for (int i 1; i n; i) { Node *node (Node *)malloc(sizeof(Node)); if (node NULL) { exit(1); } node-data i; node-next NULL; if (head NULL) { head tail node; } else { tail-next node; tail node; } } if (tail ! NULL) { tail-next head; // 首尾相连形成环 } return head; }这里有几个细节值得注意。第一malloc 的返回值一定要检查虽然课设和小程序里不检查也能跑但写成习惯以后对工程代码有益。第二链表的尾节点如果不保存 tail每次插入新节点都要从头遍历到尾部插入操作就从 O(1) 退化成 O(n)所以创建时用一个 tail 指针始终指向最后一个节点是最省事的做法。第三如果 n 是 0createLoop 应该直接返回 NULL不过在完整程序里我会在输入处拦截这种非法参数。3.2 报数出队的核心逻辑核心函数josephusKill接收一个指向起始节点的指针 cur以及报数间隔 m。函数内部第一件事是找到 cur 的前驱 prev因为只有拿到前驱才能删除当前节点。怎么找从 cur 出发绕环走一圈直到某个节点的 next 等于 cur 为止这个节点就是前驱。void josephusKill(Node *cur, int m) { if (cur NULL || m 0) { return; } Node *prev cur; while (prev-next ! cur) { prev prev-next; } while (cur-next ! cur) { // 报数 m 次移动 m-1 步 for (int i 1; i m; i) { prev cur; cur cur-next; } printf(%d , cur-data); prev-next cur-next; free(cur); cur prev-next; } printf(\n最后剩下: %d\n, cur-data); free(cur); }重点解释这个 while 循环的思路。每次进入循环时cur 指向当前报 1 的那个人prev 指向他的前驱。报数 m 其实是“当前这个人报 1然后按顺时针走到第 m 个人”所以 cur 一共要移动 m-1 步这就是为什么 for 循环的条件是i m而不是i m。很多人的 bug 就出在这里多移了一步或者少移了一步。for (int i 1; i m; i) { prev cur; cur cur-next; }移动结束后cur 指向要出列的人。此时prev正好是他的前驱执行prev-next cur-next就把 cur 从环中断开。然后 free(cur) 释放内存再把 cur 指向prev-next也就是出列者原本的下一个人。这个人在下一轮是从 1 开始报数的所以它作为下一轮循环的起点完全正确。整个 while 的退出条件是cur-next ! cur意思就是环上只剩下一个节点。当只剩一个人时它的 next 指向自己这个条件自然不成立循环停止输出最后的幸存者然后释放节点。注意这个退出条件不能写成cur ! NULL因为 cur 始终不是 NULL写成那样就是死循环。3.3 完整程序与运行效果main 函数里先读入 n、k、m做基本的合法性校验然后创建环把指针移动到第 k 个节点调用 josephusKill。int main(void) { int n, k, m; printf(请输入人数 n、起始编号 k、报数间隔 m: ); if (scanf(%d %d %d, n, k, m) ! 3 || n 1 || k 1 || k n || m 1) { printf(输入不合法\n); return 1; } Node *head createLoop(n); Node *cur head; for (int i 1; i k; i) { cur cur-next; } printf(出列顺序: ); josephusKill(cur, m); return 0; }用 n5、k1、m2 运行输出应该是出列顺序: 2 4 1 5 最后剩下: 3和我 1.1 节手推的结果一致说明逻辑正确。拿到这段代码之后我建议你把 n 改大一点比如 n41、k1、m3跑出来的幸存者是 31。这个数据是有历史背景的网上有大量验证资料可以作为测试用例。4. 边界条件与高频报错排查4.1 输入参数必须做防御性检查很多人做课设时只测了一两组正常数据就交上去了结果老师输入 n1、m1、k1 直接崩掉。这种极限输入不是刁难而是最基础的功能测试。我在 main 里拦截了 n1、k1、kn、m1 这四类非法输入保证程序不会带病运行。不过有一个情况需要特别考虑如果 k 很大比如 n5、k100题目到底怎么理解严格来说k 的范围应该限制在 1 到 n否则“第 k 个人”本身不合法。但在实际工程里我们可以把它归一化先执行k (k - 1) % n 1把 k 映射到 1 到 n 范围内再进入逻辑。这样用户即使输入一个很大的 k程序也能正常跑体验会好很多。当然如果你希望程序严格拒绝非法输入用我在 main 里的校验方式也完全没问题这两种做法取决于你的题目要求。还有 m 的取值。m1 时每次都是当前报数的人自己出列逻辑完全正确for 循环一次都不走直接删除 cur。m 很大时for 循环会绕环走很多圈功能上没毛病但是性能上会浪费这种优化我在第 5 章会提到。4.2 内存管理malloc/free 的成对与顺序C 语言最让人头疼的就是内存管理约瑟夫环的链表实现恰好把这个问题暴露得很彻底。每创建一个节点就要 malloc 一次每个删除的节点都要 free 一次最后一人的节点也要 free。如果漏掉任何一个 free程序虽然能跑但内存泄漏会在长时间运行时慢慢累积最终掏空系统内存。做实验报告时用 Valgrind 或者 Visual Studio 的调试工具检查一遍内存泄漏是很容易加分的习惯。另外一个容易踩的坑是 free 的顺序。很多人习惯先 free(cur)再访问 cur-next这就成了野指针访问。正确顺序是先把 cur 的 next 保存到 prev-next或者一个临时变量然后 free(cur)最后再让 cur 指向新的节点。我的代码里顺序是prev-next cur-next; free(cur); cur prev-next;free 之后不再访问 cur 的任何字段这是安全的标准写法。最后一个节点也有讲究。循环退出后cur是仅剩的节点打印它的 data 后马上 free(cur)。free 之后不要再用 cur也不要在别处再 free 一遍否则就是双重释放程序会直接崩溃。如果你把主函数里的 head 和 cur 混在一起用很容易出现同一块内存被释放两次的问题。4.3 报数逻辑里三个隐蔽的坑我帮同学调这道题时见过太多重复出现的错误这里挑三个最有代表性的讲。第一个坑是移动步数多算一步。报数是从当前节点开始算的当前节点报 1所以要报到数字 m只需要移动 m-1 次。如果你写for (int i 0; i m; i)就相当于数到了第 m1 个人结果自然完全错位。第二个坑是删除节点之后没有更新 cur。有些同学删完一个节点后随便把 cur 指向 head或者指向 prev导致下一轮报数的起点错了。约瑟夫环的规则是出列者下一位重新报 1也就是说删除后 cur 应该指向被删节点的后继也就是代码里的prev-next。这个位置在删除操作完成之后恰好是我们要找的下一轮起点。第三个坑是环没有真正闭合。创建链表时忘记执行tail-next head到最后遍历的时候会发现 cur 走到尾节点之后变成了 NULL程序要么崩溃要么死循环。这个坑在打印链表调试时最容易发现如果你遍历链表能停在一个 NULL 上说明环没闭合成功。提示调试链表问题时手写一张小图标出 cur 和 prev 每轮分别指向哪个节点。我第一次手动画完 n5、m2 的完整指针变化图代码里的所有问题都一眼看出来了。5. 复杂度分析从模拟到数学解的思维跃迁5.1 四种写法复杂度对照把链表、数组标记、数组前移和数学递推放在一起对比复杂度差异非常明显。解法时间复杂度空间复杂度实现难度适用场景单向循环链表O(n*m)O(n)中理解指针与环形结构数组标记法O(n*m) 且常数更大O(n)低初学快速出结果数组前移法O(n^2)O(n)低小规模数据数学递推法O(n)O(1)高难理解大规模数据仅求幸存者链表的 O(n*m) 来自每一轮都要数 m 次节点一共要进行 n-1 轮删除。当 n 和 m 都不大时这个复杂度完全够用所以它是教学演示的首选。但是假如 n1000000、m100000链表方案会慢到让人怀疑人生因为每一轮都要走非常多步总步数会膨胀得非常可怕。这时候数学递推法就体现出了碾压性优势只用一个 for 循环n 次迭代O(1) 额外空间秒出结果。数组标记法虽然时间复杂度看起来和链表一样是 O(n*m)但实际运行会慢很多因为每一轮找下一个未出列的人都要线性扫描标记数组中间跳过了大量已经出列的位置这个常数开销在 n 较大的时候非常明显。数组前移法更惨每次删除都要移动 O(n) 个元素整体 O(n^2)。所以如果是写实验报告我建议至少实现链表和数学递推数组可以当作思路补充。5.2 数学递推的推导与迁移价值数学递推法看起来是一段魔法般的代码其实背后的思路是“编号重映射”。我们先假设只有 n 个人编号从 0 到 n-1从第 0 号开始报数报到 m 的人出列。记 f(i) 为“i 个人参与游戏时最后幸存者在当前编号体系下的编号”边界是 f(1)0。现在考虑 i 个人的情况。第一个出列的人因为从 0 号开始报 1所以报到数字 m 的人编号是 (m-1) mod i。他出列后剩下 i-1 个人重新围成一个环。关键一步是从出列者的下一个人开始给剩下的 i-1 个人重新编号 0、1、2……那么原来编号为 m mod i 的人变成了新编号 0原来 m mod i 1 变成了新编号 1以此类推。新旧编号的映射关系是old (new m) mod i。既然 f(i-1) 已经告诉我们在 i-1 个人的新编号体系下幸存者的编号是 f(i-1)那么把它映射回 i 个人时的旧编号就是f(i) (f(i-1) m) mod i。这个递推式成立于是我们从 i2 一路推到 in就得到了完整答案。int josephusMath(int n, int m, int k) { int f 0; // f(1) 0 for (int i 2; i n; i) { f (f m) % i; } return (f k - 1) % n 1; // 从0编号映射回1编号并考虑从第k人开始 }为什么最后要(f k - 1) % n 1因为前面的 f 是在“从 0 号开始报数”的编号体系下算出来的而题目是从第 k 个人开始相当于把整个编号体系整体平移 k-1 位所以要先加 k-1取模后再加 1 转回 1-based 编号。这段推导如果没看懂可以找个具体的 n、m 手写一个小例子比如 n5、m2、k1手动代进去验证一遍之后再对照公式走一遍很快就能理解。这段递推的价值不仅在于解约瑟夫环它体现的“规模缩减 编号重映射”思想在很多算法题里都能复用比如循环队列的索引计算、哈希表的线性探测步长调整、以及一些需要循环滚动计算的数学问题。理解它比单纯背代码有价值得多。6. 从课设到面试环形结构能延伸到哪些场景6.1 环形结构在工程系统中的典型应用约瑟夫环本身是一个教学题但它背后的环形结构思想在真实工程系统里无处不在。最典型的就是操作系统的进程调度多个进程按顺序占用 CPU时间片用完后回到队尾等待下一轮这种“顺序轮转”和约瑟夫环的“顺时针报数”在结构上是同源的只是没有人被真正淘汰出局取而代之的是“重新排队”。再比如环形缓冲区ring buffer常见于生产者消费者模型和网络数据收发模块。固定大小的数组配上头尾指针写满了就回绕到数组头部继续写这种“回绕”能力就是理解环形结构的直接产物。你不需要真的在里面删除节点但你要能准确计算“当前位置往前走多少步”的下标这和约瑟夫环里移动 cur 指针的思维方式如出一辙。还有一个经典的变体是操作系统的 Clock 页面置换算法。它把内存中的页面组织成环形用一个指针按顺时针扫描找到第一个访问位为 0 的页面换出。这不就是“围成一圈按顺序扫描根据条件淘汰”的工程化版本吗学完约瑟夫环再去学 Clock 算法你会觉得上手特别快因为模型的骨架你已经很熟了。6.2 常见变种题型与进阶思考面试或考试里约瑟夫环还会以各种变体出现。第一种变体是只求幸存者编号不要求输出完整出列顺序。这个时候就别用链表模拟了直接上数学递推O(n) 时间和 O(1) 空间面试官会眼前一亮。第二种变体是 m 特别大。如果 m10^9每轮都从 1 数到 m 显然不现实。优化思路是利用取模运算当前环的长度是 len整圈的报数相当于转了很多圈实际有效步数只有(m - 1) % len。在链表实现里这个优化能把每轮的移动步数大幅压缩但复杂度量级仍然是 O(n*m)。在数学递推里f (f m) % i其实已经天然处理了 m 大于 i 的情况因为取模操作把超出环长的部分都折叠掉了所以数学解对付大 m 毫无压力。第三种变体是报数的起始位置不是第 k 个人而是“跳过后面的 s 个人再开始报数”。处理方式依然是把起点归一化到第 k 个人或者直接在移动步数里加上 s本质没有变化。第四种变体是每一轮报数的间隔 m 都在变比如第 1 轮报到 2 出列第 2 轮报到 3 出列第 3 轮报到 4 出列。这种问题数学递推就很难用了老老实实回到链表模拟最稳妥也最考验基本功。最后分享一个我的个人习惯写这道题时一定准备一张草稿纸把 n5、k1、m2 的出列顺序先手算出来再把代码跑出来的结果和手算结果对一遍。只要结果对不上基本就是移动步数或者前驱维护出了问题沿着 while 循环走一遍就能定位。这个习惯帮我修掉了不少看起来很玄学的 bug也建议你试试。