约瑟夫环这道题，我从大一第一次在课本里见到，到后来笔试面试前反复复习，前前后后写了不下五遍。它表面是一道经典的链表题，但用C语言去实现的时候，你会发现完全可以用三种截然不同的思路去做：循环链表、遍历数组、队列操作。三种方法各有各的思维方式，也各有各容易踩的坑。这篇文章想把这些讲透，不光给出能跑的代码，还会把每一步背后的为什么、边界条件的处理方式，以及我实际调试时遇到过的问题都翻出来聊一遍。不管是正在学数据结构的初学者，还是准备面试想快速过一下经典题的人，应该都能从里面找到值得带走的东西。
1. 先把题目说清楚：三种思路的本质区别
1.1 题面与隐藏考点
约瑟夫环的标准描述不复杂：n个人围成一圈，从第k个人开始报数，报到m的人出列，然后从下一个人重新报数，如此循环，直到所有人都出列，要求输出出列顺序或者最后一个幸存者的编号。
比如n=7，k=1，m=3，经典的输出序列是：3、6、2、7、5、1、4，最后剩下4号。
题目文字不多，但考点其实藏在两个地方。第一个是“围成一圈”——这是一个典型的环形结构，而C语言的数组和链表本质上都是线性结构，要把线性结构当环来用，就必须处理“走到末尾之后怎么回到开头”的问题。第二个是“删除出列者”——每次淘汰一个人之后，这个人就不能再参与后续报数，这就涉及数据结构的动态删除或状态标记。
这两种需求，恰好对应了三种不同数据结构的强项：链表天然适合删节点，数组适合用下标加取模模拟环形，队列则可以把“环”拆成一条不断转动的队，利用出队入队模拟循环过程。所以这道题虽然简单，却能一次性考察指针操作、数组下标管理、队列的先进先出思想，以及最基本的复杂度分析能力。
1.2 为什么同一道题要用三种方法写
有同学问过我：“能用一种方法写出来不就行了，为什么非要三种？”
这个问题我在面试中也被人反问过。我的理解是，三种方法代表的是三种抽象层次。循环链表法让你扎扎实实处理结构体的自引用和指针搬迁，练的是对链式存储肌肉记忆；数组法让你理解“删除”不一定真的删除，可以用标记位代替，练的是状态思维和取模运算；队列法要求你把环形的过程重新建模成线性队列，练的是用不同数据结构重构问题的能力。
这三样东西不是约瑟夫环特有的，它们会出现在后面的链表反转、循环队列、哈希表冲突处理等更复杂的题目里。把这道题用三种方式写一遍，相当于一次把三个基础模块都练了，性价比非常高。后面在具体场景中，你也会发现不同实现对应不同需求：游戏房间里的玩家淘汰用链表合适，嵌入式裸机环境里内存紧张可能用数组标记法，而轮询调度类的系统用队列思想更自然。
2. 循环链表实现：最贴近“环形淘汰”直觉的写法
2.1 节点结构与建环步骤
链表版的第一步是定义节点。每个节点保存一个编号和一个指向下一个节点的指针，这个没什么好犹豫的。
typedef struct Node { int data; struct Node* next; } Node;创建n个节点的循环链表时，最常见的方法是先创建头节点，再用尾插法把2到n的节点依次挂上去，最后让尾节点的next指回头节点。这一步很多人会忘记，一旦忘记成环，后面遍历就会跑到NULL上去，程序直接崩溃。
Node* createCircle(int n) { Node* head = (Node*)malloc(sizeof(Node)); head->data = 1; head->next = NULL; Node* tail = head; for (int i = 2; i <= n; i++) { Node* p = (Node*)malloc(sizeof(Node)); p->data = i; p->next = NULL; tail->next = p; tail = p; } tail->next = head; // 收尾成环 return head; }建环的逻辑非常直白：尾插的前提是保留一个tail指针，每次都从tail后面接新节点。最后一步tail->next = head是整个链表版的灵魂，没有这一步，后面的遍历就不是环而是断链。写完之后可以临时打印一圈确认next指针确实回到了head，这个小习惯能省掉很多调试时间。
2.2 报数删除的核心循环
链表版的难点在删除环节。我的写法是让一个cur指针始终指向当前报1的人，然后用一个prev指针记录它的前驱。每次从cur开始“走”m-1步，走完之后cur正好落在报m的那个人身上，prev就是它的前驱。
为什么是m-1步而不是m步？因为cur本身就在报1，所以报到m的人相当于从cur往后数第m个，也就是需要移动m-1次。这个“报数起点占了一个计数”的细节，几乎所有第一次写这道题的人都会搞错，我把这一步单独拎出来放在这里，就是为了提醒你。
void josephusCircle(Node* head, int k, int m) { Node* cur = head; // 让cur指向第k个人，即第一个报1的人 for (int i = 1; i < k; i++) { cur = cur->next; } while (cur->next != cur) { Node* prev = cur; // cur报1，走m-1步后，cur指向报m的人 for (int i = 1; i < m; i++) { prev = cur; cur = cur->next; } printf("%d ", cur->data); // 删除cur节点，cur指向下一个报1的人 prev->next = cur->next; Node* tmp = cur; cur = cur->next; free(tmp); } // 剩下最后一个节点 printf("%d\n", cur->data); free(cur); }删除这一步有三个容易出错的位置。第一，循环结束条件必须是cur->next != cur，意思是“环里只剩一个节点”，而不能用计数器判断剩余人数，因为节点的删除是物理切断指针，你不知道当前环里到底还有几个节点。第二，删除时prev->next = cur->next这一行必须写在free之前，否则这个节点的next指针已经被释放，后面的链表就断了。第三，删除后cur要立刻移动到cur->next，因为下一个报1的人就是被删除节点的后继。
2.3 链表版容易踩的几个坑
我见过最多的链表版报错，说起来其实都是同一个根源：对prev指针的更新时机没想清楚。
比如有人写删除代码时会另外用一个临时变量去遍历，结果prev没有同步跟上，导致删除时找不到正确的前驱。这种情况的表现是输出两三个数之后程序就崩溃，或者删除的节点不对。我的习惯是在每一轮循环开始前把prev初始化成cur，然后让cur在for循环里移动，prev永远跟在cur的后面，这样无论m多大，prev始终是当前cur的前驱。
还有一个坑是内存释放。链表版每次淘汰一个人都要free一个节点，如果漏掉free，程序虽然能跑，但内存会慢慢涨上去。在练习题里无所谓，但在嵌入式或长期运行的服务器程序里，这种泄漏累积起来就很麻烦。
另一个是k的语义。题目说从第k个人开始报数，这里的k通常从1开始，对应链表里第k个节点。如果把k理解为数组下标从0开始，那移位的次数就要相应减一。为了避免混乱，我习惯在开头注释写明“k从1开始”。这个注释不值钱，但能让后面读代码的人少犯迷糊。
3. 数组遍历实现：用标记代替物理删除
3.1 为什么数组不真删，而用0/1标记
数组版的核心矛盾是：数组存储是连续的，删除一个元素需要把后面的元素全部往前移，这会引入大量无意义的复制操作。于是几乎所有人都会想到一个替代方案：不真的删，而是用一个标记数组记录每个人是否还活着。出列的人标记为1，遍历时遇到标记为1的节点直接跳过。
这种做法的本质是“用状态代替结构”。如果题目只要求输出淘汰顺序或最终幸存者，不需要真正维护一个不断变短的容器，那么标记法是最高效、最好写的方案。
#include <stdio.h> #define MAXN 100 int alive[MAXN + 1]; // 0表示存活，1表示已出列 int n, k, m; // 返回pos之后下一个存活的位置，编号范围1~n int nextAlive(int pos) { do { pos++; if (pos > n) pos = 1; } while (alive[pos]); return pos; } void josephusArray(int n, int k, int m) { int remaining = n; int pos = k; // 第k个人先报1 while (remaining > 1) { // 从pos开始，移动m-1次，找到报m的人 for (int i = 1; i < m; i++) { pos = nextAlive(pos); } printf("%d ", pos); alive[pos] = 1; remaining--; if (remaining > 1) { pos = nextAlive(pos); // 从出列者的下一位重新报1 } } // 找到剩余的那个存活者 for (int i = 1; i <= n; i++) { if (!alive[i]) { printf("%d\n", i); break; } } }这个实现里最关键的是nextAlive函数。它的作用是：给出一个当前下标，返回它之后第一个存活的人。注意这里用的是do-while而不是while，因为调用者传入的pos有可能会先指向一个已出列的人，比如删除节点后pos正好落在被删除的位置上，这时候必须先往后走一步再判断。
3.2 数组法的核心逻辑：nextAlive与取模思想
nextAlive内部的循环就是一个“取模遍历”的雏形。当pos超过n时，重置为1，然后继续往后找。这种写法在数组实现中非常常见，本质就是用边界判断代替数学上的取模运算。
为什么不用pos = pos % n + 1这种写法？因为当pos从1开始时，如果你直接取模，pos等于n的时候会得到1——如果这时候用的是正序遍历，恰好是正确的。但真正的风险在于pos可能跳到0，因为如果pos等于n，pos % n等于0，这时候你还要再把0映射回n，反而多了一步容易出错的分支。相比之下，if (pos > n) pos = 1这种写法虽然看起来朴素,但它在C语言里几乎不会出错，也符合我们“编号从1到n”的直觉。
我还想多说一句：这个nextAlive函数的设计，本身就是把“环形报数”抽象成了一个“在当前存活者集合中寻找第x个”的语义。删除掉节点之后，下一次循环又从这个函数返回的位置开始，整个主循环就变得非常清爽，不需要在main函数里塞一堆下标判断逻辑。
3.3 数组版复杂度与边界细节
数组法的时间复杂度也是O(n*m)量级，因为每一轮报数都要逐个跳过已经出列的人。如果m特别大，比如m=1000000，而n只有10，那数组法会大量执行nextAlive里的查找逻辑，效率明显下降。但这个问题循环链表同样存在，因为链表法也要循环m-1次才能找到报m的人。
真正要注意的是空间复杂度。链表法需要为每个节点分配堆内存，数组法只需要一个长度为n+1的一维数组，内存占用是固定的、连续的。在内存受限的嵌入式环境或者刷题平台内存卡得紧的题目里，数组法往往更稳。
边界处理上，数组法比链表法少了一些指针悬空的烦恼，但也有自己的坑。最典型的就是k如果不在1到n范围内怎么办。我一般在函数入口做一次规范化：pos = (k - 1) % n + 1。这样不管k传进来是几，都能映射到合法编号，这个细节虽然简单，但能在考试数据比较刁钻的时候救你一命。
另一个需要注意的点是“删除最后一个活人之后”的处理。在我上面的代码里，while(remaining > 1)循环结束时其实已经找到了最后幸存的节点，直接用最后那个for循环去全表扫描，理论上可行，但如果你希望连最后一次查找也省掉，可以在while循环内部判断remaining==1时就保存结果。全表扫描的时间是O(n)，在n很大的时候不太划算，所以等会儿我可以说一个更优的处理：在循环结束后直接用pos的位置去找，但要注意pos可能落在已删除节点上，需要在查找前做一次净化。
4. 队列操作实现：把环“拉直”成一条队
4.1 队列模拟淘汰的思路来源
第三种方法是我个人觉得最有意思的，它把环形结构“拉直”成了队列。思路是这样的：把所有参与者按编号放进入队列，队头的人视为当前报数者。报数时，队头出队：如果他的报数不是m，就重新入队，放到队尾，相当于这个人绕了一圈，还没被淘汰；如果他的报数正好是m，就只出队不入队，相当于淘汰。
这个方法本质上是用“出队再入队”模拟一个人绕过一圈之后重新回到队列，用“只出队不入队”模拟淘汰。我第一次想到这个方案的时候，有种“原来队列还能这么用”的感觉。它不需要显式处理环形边界，也不需要标记数组，代码结构非常符合人的直觉。
4.2 循环队列的完整实现
用C语言写队列方案时，我推荐用数组实现循环队列。为了避免front == rear时无法区分空和满，我用一个size字段记录当前队列中的元素数量，这样判断条件就非常清晰。队列容量设为n+1，防止在极端情况下数组越界。
#include <stdio.h> #define MAXN 100 typedef struct { int data[MAXN + 1]; int front; int rear; int size; } Queue; void initQueue(Queue* q) { q->front = 0; q->rear = 0; q->size = 0; } int queueEmpty(Queue* q) { return q->size == 0; } void enqueue(Queue* q, int val) { q->data[q->rear] = val; q->rear = (q->rear + 1) % (MAXN + 1); q->size++; } int dequeue(Queue* q) { int val = q->data[q->front]; q->front = (q->front + 1) % (MAXN + 1); q->size--; return val; } void josephusQueue(int n, int k, int m) { Queue q; initQueue(&q); // 1~n全部入队 for (int i = 1; i <= n; i++) { enqueue(&q, i); } // 让第k个人成为队头，也就是第一个报1的人 for (int i = 1; i < k; i++) { int val = dequeue(&q); enqueue(&q, val); } int count = 1; while (q.size > 1) { int val = dequeue(&q); if (count == m) { printf("%d ", val); count = 1; } else { enqueue(&q, val); count++; } } printf("%d\n", dequeue(&q)); }代码的核心就是那个while(q.size > 1)循环。count表示下一个出队者应当报的数字。队头出队后，如果count等于m，说明这个人该淘汰，输出编号，count重置为1；否则这个人安全回到队尾，count加1。这个逻辑自然得几乎不需要注释。
有一点值得说明：在队列方法里，我们不需要显式地在“淘汰之后把下一个人设为报数起点”。因为淘汰的那个人出队后，队列的新队头自然就是原来在它后面的那个人。无论之前的报数进行到哪一步，队头永远对应下一个应该报数的那个参与者。这在代码上省了很多事，也避免了链表法中“删除后手动移动指针”可能引发的悬空问题。
4.3 队列方案的适用场景
队列方案的缺点是额外的空间开销。链表法只需要n个节点，数组法只需要一个n+1的标记数组，而队列方案不仅需要一个长度至少为n+1的数组来存储队列，每个未淘汰的人每轮还可能被反复地出队、入队。当m很大的时候，队列元素会被多次搬运，时间复杂度虽然仍是O(n*m)，但常数项比链表和数组都要大。
它的最大优点是逻辑简单、可读性强。如果你是在面试现场手写代码，队列方案写起来最不容易出边界bug。尤其是那种n只有几十、上百的小规模问题，完全不需要关心性能，代码的清晰反而是第一位的。
我实际写这道题的时候，有个场景让我对队列方案印象特别深：一次帮某位同学调试代码，他用链表法写出了段错误，死活找不到原因。后来我让他改用队列法重写，几分钟就写完了，问题也解决了。倒不是说链表法不好，而是当你的重心是“验证思路”而不是“练指针”时，队列方案确实是效率最高的选择。
5. 三种方法横评：复杂度、代码量与易错点
5.1 一张表看清三方案的真实差异
三种方法在时间复杂度上其实没有本质区别，都是O(n*m)量级。真正的差异集中在空间复杂度、代码可读性和出错的概率上。下面这张表是我自己整理出来做横向对比的，每次给同学讲这道题也会用它收尾。
| 对比项 | 循环链表 | 数组标记法 | 队列操作 |
|---|---|---|---|
| 时间复杂度 | O(n*m) | O(n*m) | O(n*m)，常数项略大 |
| 空间复杂度 | O(n) 堆内存 | O(n) 连续数组 | O(n) 队列数组 |
| 删除方式 | 物理删除节点 | 状态标记跳过 | 出队不入队 |
| 代码量 | 中等 | 较少 | 中等 |
| 环形逻辑 | 指针天然成环 | 下标取模 | 出队入队模拟 |
| 最容易出错的地方 | 指针悬空、free时机 | 报数步数、下标越界 | 队列容量、count重置 |
| 扩展适应性 | 适合频繁删除 | 适合内存受限场景 | 适合轮询、调度类问题 |
这张表里有一个点要特别提醒：三种方法都是O(n*m)，不是因为它们不够聪明，而是因为这道题本身就要模拟m步报数，除非用数学递推，否则任何模拟方法都躲不掉这一步。面试时如果你能主动说出“三种方法时间复杂度相同，但常数项和代码复杂度不同”，会显得思考得比较全面。
5.2 面试和考试中怎么选
如果是笔试环境，编译器不确定、调试不方便，我最推荐数组标记法。它不涉及动态内存分配，也不会出现指针悬空的问题，出bug的概率最低。
如果是面试现场，面试官明确说“你写一下约瑟夫环”，我会先看一眼他的表情再决定。如果对方是想考察基础数据结构，链表法是默认答案，因为这道题通常挂在链表的习题列表里。如果对方是考察抽象建模能力，队列方案往往会得到一些额外印象分，因为它能证明你理解了队列的语义，而不只是记住了接口。
如果你是为了期末考试复习，那三种都值得写一遍。链表练指针，数组练边界，队列练抽象。写完之后你再去面对其他环形结构题目，比如循环队列的判空判满、循环链表的合并，思路会开阔很多。
6. 实战排查与扩展思路
6.1 调试约瑟夫环的通用技巧
写这类模拟题，最难的不是主流程，而是肉眼检查输出。我调试约瑟夫环时几乎总使用下面这套流程。
先拿一张纸手动模拟一个很小的例子，比如n=5，k=2，m=2，把出列序列写下来。然后程序跑一遍，对比输出。如果完全一致，再换一组n=10，k=3，m=4继续验证。这一步能过滤掉绝大多数逻辑错误。
如果程序输出异常，就在循环里加打印语句，把每一步的当前节点或当前下标打印出来。链表版本可以打印cur->data和prev->data，数组版本可以打印pos和remaining，队列版本可以打印队头的值。对比打印结果和你纸上推演的过程，差异出现在哪一步，错误就在哪一步。
我见过的最常见的调试难点是“报数起点差一位”。这种情况通常表现为输出序列整体偏移，比如第一个出列的人是4而不是3。排查思路是验证k的定位。记住一个现实：第k个人报1，所以找报m的人要走m-1步。如果你发现自己走的步数是m步，那序列会差一位。
还有一类问题出现在循环边界。链表法最容易在n=1或者m=1时出问题。n=1时，循环链表只有一个节点，此时cur->next == cur，主循环直接跳过，输出最后一个人，这个逻辑没问题。但m=1时，每次循环都只走0步，当前报1的人直接被删，删除后cur移到下一个节点，输出序列就是从第k个人开始连续报数，这也是符合题意的。你可以用这两组特殊数据测试程序，能跑通说明边界处理基本过关。
6.2 约瑟夫环的数学解法与工程应用
三种实现都写完以后，我还想聊一个扩展，因为这道题真正进阶的玩法是用递推公式直接算出最后一个幸存者，不需要模拟任何过程。公式长这样：
f(1, m) = 0 f(n, m) = (f(n-1, m) + m) % n
这里的编号是0到n-1，算出的f(n, m)是最后一人的编号，如果题目编号从1开始，答案就是f(n, m) + 1。
这个公式的道理在于：第一轮淘汰掉报m的人之后，剩余n-1个人重新组成一个环，但这个环的起点变了，从被淘汰者的下一位开始。我们可以把这个新环重新编号为0到n-2，那么它在原环中的编号和临时编号之间就差了一个m的偏移量，取模n之后就能还原出原编号。不断倒推，就能从f(1, m)一路推回f(n, m)。
如果你把三种模拟方法都写过一遍，再来看这个公式会特别有感觉。因为你会发现，数学公式省略掉的正是循环链表中的指针移动、数组法中的nextAlive查找、队列法中的出队入队操作。这些操作在模拟过程中是重复劳动，而递推公式把它们压缩成了一个取模运算。
工程上，约瑟夫环的思想也到处可见。操作系统的进程调度里有round-robin轮转调度，就绪队列里的进程按时间片轮流执行，时间片用完的进程重新排到队尾——这几乎就是队列版约瑟夫环的翻版。嵌入式开发里的环形缓冲区，读写指针不断对容量取模，用的也是数组法里那套循环下标的逻辑。还有游戏里“每隔几个人移出房间”的淘汰机制，底层就是循环链表删除节点。
我个人在写这道题的过程中体会到的最有价值的东西，反而不是这三种数据结构本身，而是“同一个问题可以有不同的抽象方式”这件事。链表强调物理连接，数组强调状态与下标，队列强调过程流动。每次换一种抽象，你对问题的理解就会深一层。如果你现在正处于初学数据结构的阶段，我强烈建议你不要只看标准答案，而是把链表、数组、队列三个版本都亲手敲一遍。敲完后再试着用数学递推解一遍，你会有一种被打通的感觉。
