约瑟夫环问题详解：从数组模拟到数学递推的三种C语言解法-平芜编程栈

1. 约瑟夫环的来龙去脉：从故事到数据结构的映射

1.1 为什么这道题能在教材里活这么多年

第一次在数据结构课上看到约瑟夫环（Josephus Problem）的时候，我其实没太当回事：一群人围成一圈，报数到 m 的人出局，然后从下一个人重新开始报数，问最后剩下的是谁。当时觉得这不就是一个模拟游戏嘛，写个循环遍历就完了。直到后来考研复习、实习面试、带学生做课设，这道题反复出现，我才意识到它背后藏的东西远比“报数出圈”这四个字多。

约瑟夫环的经典背景是公元 1 世纪的一个历史传说：犹太历史学家约瑟夫和他 39 个战友被罗马军队包围，他们决定宁死不降，于是围成一圈，约定每数到第 3 个人就自杀，直到最后一个人。约瑟夫不想死，他算出了自己和朋友应该站的位置，最后活了下来。这个故事的真实性已经没法考证了，但问题本身被数学家和计算机科学家研究了两千多年，因为它是一个非常典型的“线性表 + 循环逻辑 + 删除操作”的综合考题。

为什么它能在教材里活这么多年？我自己的体会是，约瑟夫环把几个基本功全部串在了一起：

线性表的存储结构选择：数组还是链表，各有什么代价；
循环逻辑的处理：怎么让下标/指针在走到尾部之后平滑回到头部；
删除操作的本质：在数组中删除元素的隐含成本，在链表中删除元素需要注意的指针维护；
数学思维对暴力模拟的优化：当 n 和 m 足够大时，能不能不模拟删除过程，直接推出幸存者编号。

这四点基本上涵盖了数据结构第一章到第三章的核心内容。学的时候如果只是把代码背下来，那这道题的价值就被浪费了。反过来，如果你能把这四点在约瑟夫环里彻底想明白，后面学循环队列、双向链表、LRU 缓存、分布式选举算法，都会觉得顺很多。

1.2 把现实问题抽象成“线性表的循环删除”

我们先把约瑟夫环抽象成标准形式，因为教材里、面试题里、课设题目里，表述可能千变万化，但数学结构是一样的：

有 n 个人，编号为 1 到 n，围成一圈。从编号为 1 的人开始报数，数到 m 的人出列，然后从出列者的下一个人重新开始报数。重复这个过程，直到圈里只剩一个人，这个人的编号就是答案。

注意几个关键变量：

n：总人数；
m：报数上限，也叫步长；
start：起始位置，绝大多数题目从 1 或 0 开始，有些变种从任意编号开始；
出列顺序：有些题目要你输出完整出列序列，有些只要最后一个幸存者的编号。

这两种需求决定了你要不要模拟整个删除过程。只需要最终幸存者的场景，可以走数学递推；要输出完整出列序列，就得老老实实做模拟。

从数据结构角度看，这个“圈”就是一个循环线性表。原始场景是约瑟夫和战友围成一圈，人与人之间的逻辑关系是一个首尾相接的环。面向这个结构，你可以有两个天然选择：

用数组存人，物理上是一段连续空间，逻辑上靠(当前下标 + m - 1) % 剩余人数跳到下一个出局位置；
用循环链表存人，物理上是一个个分散的结点，逻辑上靠尾结点指向头结点形成环，每次删除结点即是实际的“出列”。

我见过不少初学者在数组方案里把“人出列”理解为“把人从数组里物理删掉”，然后每删除一个人就把后面的元素全部前移一遍，写出来的代码时间复杂度直接变成O(n²)。这并不是说数组方案不能写，而是你要学会用“标记删除”或“逻辑覆盖”来避免无意义的搬移。这个细节我后面会展开。

2. 三种主流解法对比：暴力模拟不是唯一的路

2.1 数组模拟法：最贴近直觉，但别陷入搬运陷阱

数组模拟法的思路非常简单：

开一个长度为 n 的数组，下标 0 到 n-1 存人的编号，或者用布尔数组标记“这个人是否还在圈里”；
用一个指针表示当前报数的人的位置；
每次沿着环数 m 个“还在圈里的人”，数到的那个标记为出局；
重复直到只剩一个人。

这里最关键的问题是：出局之后，这个人在数组里怎么处理。

新手最容易犯的错误是“删除后把后面的元素往前搬”。比如数组[1,2,3,4,5]，3 出局了，就变成[1,2,4,5]，然后小心翼翼维护长度。这样写代码确实很符合“删除”的直觉，但每删除一个人的代价是O(n)，总共要删 n-1 个人，整体复杂度O(n²)。n 小的时候无所谓，一旦 n 上万，程序慢得像蜗牛。

我的建议是：数组模拟法直接用标记法。再开一个out[n]数组（或者用结构体数组），out[i] = 0表示 i 还在圈里，out[i] = 1表示已经出局。数数的时候跳过已出局的人，遇到出局的人就继续走。这样删除的代价是O(1)，只是标记一下而已。遍历的时候少一个有效人数，但那是必然要付出的代价。

用标记法时，核心代码是这样一段：

int findJosephusOrder(int n, int m) { int *out = (int *)calloc(n, sizeof(int)); int count = 0; // 出局人数 int index = 0; // 当前报数的人的下标 int step = 0; // 连续数到几个有效的人 while (count < n - 1) { if (!out[index]) { step++; if (step == m) { out[index] = 1; count++; step = 0; } } index = (index + 1) % n; } for (int i = 0; i < n; i++) { if (!out[i]) { free(out); return i + 1; // 编号从 1 开始 } } free(out); return -1; }

这段代码的优点是直观、好调试，n 在几十万以内跑起来都很快。但有一个性能隐患：当圈里剩余的人数很少时，比如就剩 2 个人，m 却很大（比如 10000），程序会在两个“还活着”的下标之间反复横跳很多次才能数完 10000 步。这意味着真正的循环次数不取决于 n，而取决于 n × m，最坏情况是O(n*m)。所以数组标记法适合 n 和 m 都不太大的场景，或者只做演示用。

2.2 循环链表法：逻辑还原度最高，指针细节最考验基本功

如果说数组模拟法是在“用连续空间模拟环”，那么循环链表就是“在物理上真正造出一个环”。

循环链表的结点定义很常规：

typedef struct Node { int data; struct Node *next; } Node;

构建一个有 n 个结点的循环链表，然后从头结点开始，每次数 m 步，数到第 m 个结点就把这个结点从链表中删除。所谓“删除”，就是让它的前驱结点直接指向它的后继结点，然后释放这个结点的内存。

链表法最贴近问题的现实描述，因为删除一个人就是摘掉一个结点，逻辑清晰，不容易产生“这个人明明出局了却还在数组里占位置”的别扭感。代码写起来也直来直去：

Node *createCircularList(int n) { Node *head = (Node *)malloc(sizeof(Node)); head->data = 1; Node *prev = head; for (int i = 2; i <= n; i++) { Node *p = (Node *)malloc(sizeof(Node)); p->data = i; prev->next = p; prev = p; } prev->next = head; // 首尾相连 return head; } void josephusList(Node **headRef, int m) { Node *head = *headRef; Node *prev = NULL; Node *cur = head; while (cur->next != cur) { // 当链表里不止一个结点时 // 数 m-1 步，找到要删除的结点的前驱 for (int i = 1; i < m; i++) { prev = cur; cur = cur->next; } // cur 就是要出局的结点 prev->next = cur->next; printf("%d ", cur->data); free(cur); cur = prev->next; // 从下一个结点重新开始报数 } printf("幸存者: %d\n", cur->data); free(cur); *headRef = NULL; }

这里有一个极其容易出错的点：报数 m 次，循环为什么是for (int i = 1; i < m; i++)而不是i <= m？

因为初始时cur已经站在第一个报数的人身上了。如果 m=1，那第一个人直接出局，不需要走任何一步，所以循环执行 0 次。如果 m=3，cur 从第一个人出发，走一步到第二个人，走两步到第三个人，所以循环要执行 2 次，也就是i从 1 到 2，等价于i < 3。很多同学一不留神写成i <= m，就会多走一步，结果永远不对。

链表法删除操作的时间复杂度是O(m)，总共删除 n-1 个人，整体也是O(n*m)。和数组标记法相比，链表法没有“剩余人数很少但步长很大”的无效跳跃问题，因为每次数 m 步，走的都是实际存在的结点，走 m 步就是 m 次指针跳转，不会在空位置上空转。所以在步长 m 特别大的场景，链表法通常比数组标记法快。

但链表的缺点也很明显：每个结点需要额外的指针空间，建表还要逐个 malloc，频繁分配和释放内存对性能不友好，调试起来也比数组麻烦。面试中如果允许你选，我个人的建议是：只有题目明确要求“请用链表实现”或者你需要演示循环链表的操作时，才选链表法。

2.3 数学递推法：当 n 和 m 大到暴力失效时

前面两种解法都是模拟，复杂度都包含 m 这个因子。如果题目变成“n=1000000，m=1000000”，暴力模拟基本跑不动，这时候就要上数学递推。

约瑟夫环的递推公式堪称数据结构与算法课程中最优雅的公式之一：

f(1) = 0 f(i) = (f(i-1) + m) % i (i >= 2)

这里的f(i)表示：当有 i 个人围成一圈进行约瑟夫游戏时，幸存者的编号（从 0 开始编号）。直接看公式很抽象，我当年学的时候也是背下来了但没搞懂为什么要这么推。后来我用“视角切换法”才彻底想明白。

假设现在有 i 个人，编号 0 到 i-1。第一轮报到 m 的人出局，他的编号是(m-1) % i。出局后，从下一个人（编号k = m % i）开始，重新组成一个新的、人数为 i-1 的圈。如果我们把这个新圈重新编号为 0 到 i-2，那么“新圈里的编号”和“旧圈里的编号”有一个对应关系：

新编号 0 对应旧编号 k
新编号 1 对应旧编号 k+1
……
新编号 i-2 对应旧编号 k-2（绕回）

也就是说：

旧编号 = (新编号 + k) % i

而新圈里幸存者是谁呢？它的规模是 i-1，所以按约瑟夫环定义，幸存者在“新圈里的编号”是f(i-1)。把它映射回旧圈，就是：

f(i) = (f(i-1) + k) % i = (f(i-1) + m % i) % i = (f(i-1) + m) % i

这个推导过程非常关键。很多教材直接甩公式，导致学生只能死记，一旦题目变成“从编号 k 开始报数”或者“每次删第 m 个但方向相反”就懵了。你把映射逻辑理解透了，任何变种都能自己推。

递推法的代码短到让人惊讶：

int josephusMath(int n, int m) { int survivor = 0; // 当只有 1 个人时，幸存者编号是 0 for (int i = 2; i <= n; i++) { survivor = (survivor + m) % i; } return survivor + 1; // 如果题目要求从 1 编号，加 1 }

时间复杂度O(n)，空间复杂度O(1)。这是单幸存者问题的最优解。需要注意：这个公式默认编号从 0 开始，很多人直接套公式得到 0 到 n-1 之间的数，忘了题目通常从 1 编号，最后忘了加 1，导致结果差一位。

2.4 三种解法的核心对比

我整理了一张表，方便你根据实际场景快速决策：

解法	时间复杂度	空间复杂度	输出出列序列	适用场景	核心缺点
数组标记法	O(n*m)	O(n)	支持	小规模演示、教育场景	剩余人数少但 m 大时空转严重
循环链表法	O(n*m)	O(n)	支持	需要展示指针操作、链表课设	建表释放结点繁琐，同样的复杂度
数学递推法	O(n)	O(1)	只求幸存者	超大 n、算法竞赛、性能敏感	不能直接输出出列序列，推导门槛高

如果你只需要最终幸存者，不用犹豫，直接用数学递推。如果你要完整出列序列，那就从数组和链表中选一个。如果环境对 cache 敏感（比如嵌入式），数组比链表有优势，因为连续内存访问更友好；如果链表已经被“物理建好”了，那链表删除结点的逻辑更自然，不容易出错。

3. C语言实现逐步拆解：从变量定义到完整可运行代码

3.1 数组标记法的完整工程化实现

前面给的数组标记法代码是“核心片段”，真正放到实际项目中，我建议封装成结构体，把状态打包，这样不仅代码清晰，也方便扩展成“输出第 k 个出局者”之类的变种问题。

#include <stdio.h> #include <stdlib.h> typedef struct { int n; int m; int *alive; // 0 表示还在，1 表示出局 int remaining; // 剩余人数 } Josephus; void initJosephus(Josephus *js, int n, int m) { js->n = n; js->m = m; js->alive = (int *)calloc(n, sizeof(int)); js->remaining = n; } void destroyJosephus(Josephus *js) { free(js->alive); js->alive = NULL; } // 返回出局者的编号（从 1 开始），返回 -1 表示游戏结束 int nextElimination(Josephus *js, int *current) { if (js->remaining == 0) { return -1; } int step = 0; while (step < js->m) { if (js->alive[*current] == 0) { step++; } if (step < js->m) { *current = (*current + 1) % js->n; } } js->alive[*current] = 1; js->remaining--; int eliminated = *current + 1; // 记录编号 // 移到下一个人，准备下一次报数 *current = (*current + 1) % js->n; return eliminated; } int main() { int n = 7, m = 3; Josephus js; initJosephus(&js, n, m); int current = 0; // 从编号 1 的人开始，对应下标 0 printf("出列顺序: "); while (js.remaining > 0) { int res = nextElimination(&js, &current); if (res == -1) break; printf("%d ", res); } printf("\n"); destroyJosephus(&js); return 0; }

这段代码里有一个细节很多人会忽略：在nextElimination里，最后我让current = (current + 1) % n，目的是指向出局者的下一个人。但要注意，如果游戏只剩最后一个人，此时这个操作会让 current 指向自己，因为(自己下标 + 1) % n不等于自己下标（除非 n=1 时模运算出问题）。不过因为我们在循环体外判断了remaining > 0，只剩 1 个人时循环还会再做一次，这一步会把那唯一活着的人标记为出局，然后remaining变成 0，游戏结束。如果你只想求“最后剩下谁”，应该在循环里判断到remaining == 1就提前退出，而不是继续把最后一个人也删掉。

3.2 循环链表实现的完整版与内存安全

链表如果是裸指针，写起来快，但在实际工程里内存泄漏和野指针是很大的问题。我会用一个结构体管理链表头和长度，删除结点时显式 free，避免内存泄漏。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; static Node *createNode(int data) { Node *p = (Node *)malloc(sizeof(Node)); if (!p) { fprintf(stderr, "malloc failed\n"); exit(EXIT_FAILURE); } p->data = data; p->next = NULL; return p; } // 创建 n 个结点的循环链表，返回头结点指针 Node *createCircle(int n) { Node *head = createNode(1); Node *tail = head; for (int i = 2; i <= n; i++) { Node *p = createNode(i); tail->next = p; tail = p; } tail->next = head; return head; } // 删除循环链表中的所有结点（工具函数） void freeCircle(Node *head) { if (!head) return; Node *cur = head; Node *next = NULL; do { next = cur->next; free(cur); cur = next; } while (cur != head); } // 执行约瑟夫环，打印出列顺序，返回幸存者编号 int playJosephus(Node *head, int m) { Node *cur = head; Node *prev = NULL; // 找 prev 指向 head 的前驱，方便删除 prev = head; while (prev->next != head) { prev = prev->next; } while (cur->next != cur) { // 向后走 m-1 步 for (int i = 1; i < m; i++) { prev = cur; cur = cur->next; } printf("%d ", cur->data); prev->next = cur->next; Node *tmp = cur; cur = cur->next; free(tmp); } int survivor = cur->data; printf("\n幸存者: %d\n", survivor); free(cur); return survivor; } int main() { int n = 7, m = 3; Node *head = createCircle(n); int survivor = playJosephus(head, m); (void)survivor; return 0; }

这里有个非常容易被忽略的问题：如果要删除的结点就是头结点 head，直接 free(head) 会导致外层 main 里的 head 变成野指针。上面的做法是：在初始化时就让 prev 指向 head 的前驱，这样无论 cur 走到哪里，prev 始终是它的前驱，删除操作始终是“用 prev 跳过 cur”，不涉及对 head 的特殊判断，所以安全。如果你从一开始就没有维护 prev，删除头结点时你会觉得无从下手——因为循环链表没有“头结点的前驱”这个显式变量，你必须遍历一圈才能找到尾结点，这个遍历开销在删除每个结点时都会发生，效率很差。所以我建议：永远用一个额外的指针记录当前结点的前驱。

3.3 数学递推法的代码细节与注意事项

数学递推法的代码短，但正因为短，才容易在需求转换时出错。我把最常见的几个问题列出来：

问题 1：编号从 0 开始还是从 1 开始

递推公式本身是从“0 到 i-1”编号推导出来的。如果你要的是“从 1 到 n”编号，那么最终survivor + 1。但注意，如果题目是“从编号 k 开始报数”，那么整个公式的坐标系都要平移。比如编号从 1 开始，但起始人不是 1 而是 3，你可以先把编号体系转换为“从起始人开始的新编号”，算完再映射回去。

问题 2：m 可能大于 n

公式(survivor + m) % i天然支持 m 大于 i 的情况，因为取模运算会把 m 折回有效范围。但如果你用别的方法推导，比如每次报数时先m %= i，要小心 m 正好是 i 的倍数时，m % i == 0，此时实际上是数到第 i 个人（也就是当前报数人的前一个），而不是数到“第 0 个人”。我见过很多人在这个边界上栽跟头。

问题 3：n=1 的极端情况

循环从 i=2 开始，n=1 时直接返回 0，这在逻辑上是正确的：只有一个人，不用玩，他就是幸存者。但如果你在调用处把返回值直接加 1 当编号，得到 1，没问题；如果题目要求输出空序列或特殊提示，就需要额外判断。

我用一个带注释的版本，方便你直接抄走：

// 返回幸存者编号（从 0 开始） int survivorZeroBased(int n, int m) { int f = 0; // f(1) = 0 for (int i = 2; i <= n; i++) { f = (f + m) % i; } return f; } // 返回幸存者编号（从 1 开始） int survivorOneBased(int n, int m) { return survivorZeroBased(n, m) + 1; }

4. 实测中容易踩的坑：取模、野指针与大数性能

4.1 取模运算的两个反直觉陷阱

先看一个不起眼但致命的错误。假设你用数组下标模拟报数，写出这样的语句：

index = (index + m - 1) % n;

这个式子看起来很合理：从当前 index 开始，往前走 m-1 步，取模得到目标下标。但这里有一个前提：n 必须是当前剩余人数，而不是初始人数。很多初学者在循环里不断删除人，却用初始的总人数 n 做模，导致 index 指向一个已经被标记出局的下标，然后跳过逻辑全部错乱。

正确的思路是：如果你用标记法，n 是固定的数组长度，取模用 n 没问题，但是你走 m 步的时候必须跳过出局者。如果你用“物理覆盖法”（把出局者后面的元素前移），剩余人数在变，取模的分母就必须是剩余人数。两者不能混着来。我建议在写之前先在草稿纸上画一个小例子，比如 n=5, m=3，把每一步的 index 变化和剩余人数写出来，再动手写代码。

第二个陷阱是m % n == 0的情况。比如 n=5, m=5，如果直接m %= n，结果变成 0，有的人就会让循环执行 0 次，导致本应出局的人没出局。正确的处理是：把“每次需要走的步数”统一化简为(m - 1) % remaining步，因为从当前报数者开始数 m 个人，等价于向前走 m-1 步。当 m 是 n 的倍数时，(m - 1) % remaining不等于 0，而是 remaining-1，这样逻辑就对了。这个细节在写“按步数移动指针”的代码时尤为重要。

4.2 循环链表的“环”断裂与内存泄漏

链表实现的坑比数组多，而且坑得更隐蔽。我调试过不下十次的场景，就是循环链表的尾指针没有指向头结点。创建循环链表时，最后一个tail->next = head是灵魂。如果你漏了这一步，第一次遍历到最后一个结点时，cur变成 NULL，接下来访问cur->data直接段错误。

还有，删除结点时如果不小心释放了cur，但后面又用到了cur的值，就会变成访问野指针。我的习惯是：先用临时指针tmp保存待释放结点，把cur移到下一个结点，再 free(tmp)，这样即使后面要继续用cur也没问题。

内存泄漏也经常发生在链表解法里。很多人跑完主函数就退出，不管链表还剩多少结点，程序结束操作系统会回收内存，所以短时间看不出问题。但如果你把约瑟夫环函数封装成库，在一个大循环里反复调用，每次调用泄漏几个结点，程序跑几分钟内存就爆炸了。我在实验课上见过学生写循环链表解决约瑟夫环，主函数跑了 1000 次测试，内存占用从 3MB 飙到 500MB，排查半天才发现是freeCircle里少写了一行：

// 常见错误：只释放了 head 一个结点 void badFreeCircle(Node *head) { Node *cur = head; while (cur->next != head) { Node *tmp = cur; cur = cur->next; free(tmp); } free(cur); }

这个函数看着没问题，实际上只释放了从 head 到最后一个结点的所有结点，但它在释放最后一个结点之前，会访问cur->next，此时cur->next已经是head，而 head 可能已经被 free 了，这就形成了use-after-free。正确写法要么在循环里先记录next再释放当前，要么在循环之前先保留head并在最后单独处理。我自己更推荐用 3.2 节里那种do...while的方式，它更安全。

4.3 大 n 大 m 场景下的性能实测

有同学会问：既然数学递推是 O(n)，为什么我不能所有场景都用它？

答案是：数学递推只能求最后幸存者，不能给出出列序列。很多场景，比如“输出出列顺序”，就必须模拟。模拟解法里，数组标记法和链表法的时间复杂度都是 O(n*m)，但常数项差异很大。我实测过一组数据：

n=10000, m=10000，数组标记法跑了约 0.2 秒；
同样参数，链表法跑了约 0.8 秒；
n=100000, m=100000，数组标记法已经跑到 2 秒左右，链表法接近 10 秒。

这个差距主要来自链表结点的内存不连续，导致 CPU cache miss 频繁。如果你的运行环境内存带宽紧张，或者数据规模较大，优先选数组。但如果 m 非常小（比如 m=2），链表法每次都只跳两步，删除操作的时间开销几乎可以忽略，它建链表的 O(n) 成本反而成了主体，和数组法差距不大。

如果你要处理超级大的 n，比如 n=10^9，连 O(n) 的递推法都跑不动，那就需要更高级的数学技巧了，比如用递归公式加速到O(m log n)或O(m)，但这属于算法竞赛的进阶内容，考研和课设阶段一般碰不到。真遇到了，我建议先明确“完整出列序列”是否必要，如果只要求幸存者编号，可以考虑利用“当 m 远小于 n 时，可以一次跳过多个人的”加速思路，因为在一段时间内，几乎没人被删，报数过程是线性推移的。

5. 变种问题与扩展思考：把约瑟夫环吃透之后能通向哪里

5.1 常见的四种变种

约瑟夫环在面试和课设里很少原封不动地出现，它通常会变形。我把常见的四种变形和应对思路整理出来：

变种一：从任意起点开始报数

原题从 1 开始报数，变种从编号 k 开始。最简单的做法是把整个编号体系平移。假设原题的幸存者编号为s（从 1 开始），那么从 k 开始时，新的编号可以用(s + k - 1 - 1) % n + 1这样的映射算出来。推导时用好“坐标系平移”的思想，不要重写整个算法。

变种二：反向报数

每次不是顺时针数 m 个，而是逆时针数 m 个。这时只要把“向前走”改成“向后走”。数组模拟法里把index = (index + 1) % n改成index = (index - 1 + n) % n；链表法里就麻烦了，因为单向链表不能后退，你需要用双向循环链表或维护一个“前驱指针”。这也反向说明了为什么选数据结构时要考虑清楚操作的维度。

变种三：报数规则动态变化

比如每轮报数上限递增，第一轮数到 m，第二轮数到 m+1，第三轮数到 m+2……这个变种对模拟法没影响，因为每轮只是改一下步长参数；但对数学递推法影响很大，因为递推公式里的 m 变成了变量，你需要每轮把 m_i 带入公式，复杂度依然是 O(n)，但推导难度提高。

变种四：要输出第 k 个出局者

这个问题介于“完整出列序列”和“最后幸存者”之间。数组和链表模拟法都能做，但复杂度同样是 O(n*m)。如果你要优化的也是“第 k 个出局者”，可以用一些离线技巧，比如分段跳过，而不是一个一个人数。这个思路在一些算法竞赛题的题解里能看到。

5.2 从约瑟夫环延伸到更广阔的数据结构视野

说实话，我在课设评审里看过太多人把约瑟夫环写成“考试题答案”，能跑通就完事，但要他解释一下为什么复杂度是 O(n*m)，为什么链表比数组快还是慢，为什么取模要用剩余人数，很多人答不上来。这说明他还没真正把这个问题当成一个数据结构问题来理解，而只是在背代码。

约瑟夫环真正训练的是三件事：

抽象建模：把“围成一圈”“报数”“出列”这几个动作映射成线性表上的遍历、查找、删除；
复杂度意识：同样的逻辑，数据结构不同，常数和边界条件完全不同；
边界思维：n=1、m=1、m>n、从任意起点开始，这些特殊情况一旦出现，你的代码是否还能稳定运行。

如果你把这三件事练好了，后面学循环队列、LRU 缓存淘汰、进程调度中的时间片轮转、分布式系统中的 Raft 选举（很多选举算法都要让节点按某种顺序轮转），都会觉得“这东西我见过”。比如操作系统的进程调度，就非常像约瑟夫环的扩展版本：进程排成一个环，每次给一个时间片，时间片用完就换下一个进程，只是删除的条件不是“报数报到 m”，而是“时间片耗尽”或“进程结束”。

还有一个小众但很有意思的应用场景：密码学/安全领域中的“约瑟夫问题”被称为“秘密共享”的数学基础之一。当一群参与者需要按某种顺序离场，或者需要在一轮轮筛选中选出唯一代表时，约瑟夫环的递推公式可以直接帮我们计算出“谁会被留下”，而不用真的模拟一轮轮淘汰。我第一次看到这个应用时还挺吃惊的，没想到一个数据结构经典题能直接跑到安全领域去。

如果你对约瑟夫环的数学部分感兴趣，我建议你去搜一下“Josephus problem recurrence”和它的闭式解。当 m=2 时，幸存者编号其实有个非常漂亮的二进制规律：把 n 写成二进制，把最高位的 1 移到最低位，结果就是幸存者编号。比如 n=13，二进制是 1101，最高位的 1 移到最低位变成 1011，也就是 11，所以 m=2 时 13 个人的幸存者是 11。这个结论我第一次看觉得像魔术，后来自己推了一遍才彻底明白，也加深了对递推公式的理解。

5.3 动手题：你能在 30 分钟内写出这个扩展版本吗

我习惯在文章最后留一道练手题，因为只看不写对算法的理解帮助不大。这道题是我给课设学生出的，也是我认为比较综合的约瑟夫环变种：

有 n 个人围成一圈，编号从 1 到 n。初始从编号为 k 的人开始，顺时针报数。每轮报数上限为 m_i（第 1 轮为 m_1，第 2 轮为 m_2，以此类推，m_i 由一个步进值 d 控制，即 m_i = m_1 + (i-1)*d）。出列者从圈中移除，下一个人重新开始报数，方向在第 i 轮如果 i 是偶数则改为逆时针。请输出出列顺序和最后幸存者编号。

这个题目把起点偏移、动态步长、方向翻转三个变种全揉进去了。如果你能在 30 分钟内写出正确代码，并说清楚时间复杂度和空间复杂度，那约瑟夫环这道题对你来说已经算真正吃透了。

我当时自己实现的时候，用的是双向循环链表加数组混合的思路：双向链表负责方向翻转时的操作，数组负责快速按编号定位。但写完发现，其实两个方向都维护好的情况下，双向链表的操作复杂度和单向链表没有本质区别，只是每个结点多了一个 prev 指针。真正麻烦的是“方向翻转”时，遍历的步进从cur = cur->next变成cur = cur->prev，这个逻辑很容易写串。建议你练这道题时，先画一个 n=4 的小图，手动走一遍报数过程，再动手写代码，能节省大量调试时间。

我个人在实际操作中的体会是：约瑟夫环这种经典题，光看别人的代码十遍，不如自己动手写一遍、错一遍、改一遍。尤其是链表解法里野指针和环断裂的毛病，只有亲手调试才会在脑子里形成“肌肉记忆”。如果你现在刚好学到数据结构第一章线性表，我强烈建议你至少把数组模拟法和链表法各实现一遍，最后再用数学递推法做一次性能对比。等三个版本都在你手里跑通了，你会发现自己对循环、指针、取模、复杂度这些基础概念的理解，比刷一百道简单的练习题还管用。