约瑟夫环这道题，写过的同学都知道，说穿了就是循环链表加两个指针来回挪，但当初我为了把它调通，愣是在宿舍debug到凌晨。后来把“前驱指针”的思路理顺了，再回头看，其实这个题目考的就两件事：把环形结构想清楚，以及安全地删除一个链表节点。

这篇文章我会用C语言完整拆解约瑟夫死亡游戏，从数据结构选型、循环链表的构建、报数出列算法，到数组模拟、数学递推公式，最后附上我实际调试时踩过的一堆坑和测试建议。适合正在做课程设计、准备数据结构考试，或者自学链表想找点实战项目的朋友。

1. 约瑟夫问题到底在考什么：循环链表的本质

1.1 问题描述与建模思路

约瑟夫问题最早来源于一个古老的传说故事：一群人围成一圈，按某种规则依次淘汰，最后只剩下一个人。放到数据结构里，标准描述是：n个人编号为1到n，围坐在一张圆桌周围，从编号为1的人开始报数，数到m的人出列，然后从下一个人开始重新报数，如此循环，直到所有人都出列。题目通常要求输出出列顺序，或者求出最后剩下的幸存者编号。

我第一次拿到这个题目时，第一反应就是：这不就是一个循环遍历删除的过程吗？确实如此。整个流程抽象出来，包含三个核心动作：沿着圈移动指定的步数、标记当前位置出列、从下一个位置继续。这三个动作不断重复，直到圈内没有元素为止。

这里有个容易忽略的地方：题目里的“报数”是有方向性的，始终沿着圆桌的同一方向前进，并且报数起点是上一个出列者的下一位。这意味着数据集合必须支持“绕回头”的遍历方式。如果用数组写，你需要在访问到末尾时手动把下标重置为0；如果用链表写，则天然支持从头绕回。所以这道题目的建模关键，就是找出一种能自然表达“环形遍历”的数据结构。

1.2 为什么循环链表是首选方案

教科书和大多数习题把约瑟夫环放在“链表”章节，不是没有原因的。它的核心操作是反复删除节点，而单链表和循环链表删除节点只需要O(1)的指针修改操作，不需要搬运数据。相比之下，顺序表删除元素需要把后面的元素整体前移，最坏情况是O(n)，在n较大的时候开销很可观。

另外一点很关键：循环链表的next指针天然形成了“环形”的拓扑结构，插入、删除、绕圈遍历都符合约瑟夫环的运行语义。你不用像数组那样在每次到达尾部时判断一下“该不该绕回0号下标”，结构本身就帮你处理了边界。

不过实话实说，这不是唯一能做的方案。数组加状态标记也能模拟出列过程，只是逻辑删除后仍需遍历剩余元素，时间复杂度会高一些。我把数组模拟和数学递推放在第4章详细对比，那种方案代码更短，但可解释性和教学价值不如循环链表。如果目标是“理解数据结构如何解决实际问题”，循环链表是最贴题的选型。

1.3 复杂度分析与整体设计

在链条很长的场景下，每轮从报数开始到找到出列者，需要移动m步，每移动一步就是一次p = p->next操作，所以单轮复杂度是O(m)。总共n个人出列，整体复杂度是O(n × m)。这个复杂度不算优秀，但对于课程设计和入门学习完全够用，因为重点是通过代码理解链表操作的本质。

如果想优化，可以使用数学递推公式把时间复杂度降到O(n)，但那只适合求解最后一个幸存者的编号，无法输出完整出列顺序。所以我的方案是：主实现采用循环链表，保留完整的出列过程；额外提供一个数组模拟和一个数学公式实现，用于对比和扩展。

整体设计上，我先实现一个环形链表的构建函数，再做约瑟夫环出列函数，最后在main函数中串起来。为了让代码可读性更高，我还会加一个打印循环链表的辅助函数，方便调试时确认链表结构是否正确。

2. 从节点到循环链表：核心数据结构一步步来

2.1 节点结构体与基本约定

链表的基本单位是节点。约瑟夫环里每个节点代表一个参与游戏的人，节点里需要存储两样东西：这个人的编号，以及指向下一个人的指针。

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

这里有个初学者容易纠结的问题：data用什么类型。约瑟夫环的编号是正整数，用int就够了。如果你以后想扩展成存储字符串姓名或者更复杂的信息，可以把data替换成更复杂的结构体，但这道题没必要。

再来说说“头节点”的问题。我在教学代码中看到很多版本会创建一个不存数据的头节点，再用它来管理循环链表。但约瑟夫问题描述的是一圈人，没有“空节点”的概念，所以代码里我不会引入单独的头节点，而是直接让第一个实际节点充当“入口”。

这样做有个好处：打印链表时，从任何一个节点出发绕一圈就能看到全部节点；出列时，所有节点都是实际参与者，不存在跳过哨兵节点的判断。缺点是需要小心处理空链表，不过输入n>=1时不会出现空链表。

2.2 创建循环链表：尾插法与成环

构建一个包含n个节点的循环链表，通常使用尾插法：每次在链表尾部追加新节点，最后把尾部节点的next指向头部节点。

Node *createLoop(int n) { Node *head = NULL; Node *tail = NULL; for (int i = 1; i <= n; i++) { Node *node = (Node *)malloc(sizeof(Node)); if (node == NULL) { printf("内存分配失败\n"); exit(1); } node->data = i; node->next = NULL; if (head == NULL) { head = node; tail = node; } else { tail->next = node; tail = node; } } if (tail != NULL) { tail->next = head; } return head; }

第i个节点的data就是编号i，这样编号天然有序。第一次插入时head和tail都指向同一个节点；后续每次插入，新节点挂在tail后面，tail再往后移动。

最关键的一行是tail->next = head;。如果漏掉这一行，链表就是一个普通的单链表，约瑟夫环跑起来会直接越界到NULL，程序大概率崩溃。我当年第一次写就栽在这，后面第5章会专门讲这个坑。

这里顺带说明一下：为什么malloc之后要检查返回值？在很多比赛和课程评测环境里，内存分配失败会直接导致段错误，提前检查并报错，能让问题早点暴露。虽然是加分项，但养成了好习惯。

2.3 构建辅助函数：打印循环链表

调试链表题最朴素的方法就是把整个链表打印出来。循环链表不能像单链表那样用while (p != NULL)判断结束，因为环形结构里next永远不会是NULL。正确的打印方式是：记录起始节点，当遍历回到起始节点时停。

void printLoop(Node *head) { if (head == NULL) { printf("空链表\n"); return; } Node *p = head; do { printf("%d ", p->data); p = p->next; } while (p != head); printf("\n"); }

为什么用do-while而不是while？因为初始状态下p就是head，如果用while判断p != head，第一次循环体根本不会执行，打印结果就是空的。do-while保证至少执行一次，正好符合“先打印，再判断是否绕回起点”的逻辑。

我在实际调试时发现，这个打印函数的价值不仅在于验证链表创建是否正确，还在于观察每轮出列后链表的状态。你可以在josephus函数里每删除一个节点就调用一次printLoop，配合打印输出能非常直观地看到节点是怎么一步步减少的。

3. 核心逻辑实现：报数、出列与链表删除

3.1 关键算法：p始终指向前驱，而不是待删节点

这是整篇代码里最核心的思路，也是我当初卡壳最久的地方。单链表删除一个节点，必须知道它的前驱节点，才能把前驱的next指向被删节点的下一个节点。约瑟夫环里的删除操作每轮都在做，所以最稳妥的做法是：维护一个指针p，让它始终指向“当前报数为1的那个人”的前驱节点。

这样做的好处是，当需要删除某个节点时，这个节点就是p->next，我们只需要执行p->next = p->next->next，再free掉p->next，不需要额外找前驱。

为什么这么设计？你可以想象成一个接力棒：p本身永远不参与报数，它只是站在报数起点前一个位置，它的next指向报数起点。每报一个数，p就顺着环走一步；当报完m个数后，p恰好停在待删除节点的前驱。删除完成后，p->next自然指向下一轮的报数起点，接力棒无缝交接。

3.2 完整代码与运行效果

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node *createLoop(int n) { Node *head = NULL; Node *tail = NULL; for (int i = 1; i <= n; i++) { Node *node = (Node *)malloc(sizeof(Node)); if (node == NULL) { printf("内存分配失败\n"); exit(1); } node->data = i; node->next = NULL; if (head == NULL) { head = node; tail = node; } else { tail->next = node; tail = node; } } if (tail != NULL) { tail->next = head; } return head; } void printLoop(Node *head) { if (head == NULL) { printf("空链表\n"); return; } Node *p = head; do { printf("%d ", p->data); p = p->next; } while (p != head); printf("\n"); } void josephus(Node *head, int n, int m) { if (head == NULL) { return; } Node *p = head; // 让 p 指向尾节点，也就是头节点的前驱 while (p->next != head) { p = p->next; } while (p->next != p) { // p 始终指向报数起点位置的前驱 // 报到 m 的人出列，所以 p 需要向后移动 m-1 次 for (int i = 1; i < m; i++) { p = p->next; } Node *del = p->next; printf("%d ", del->data); // 删除 del p->next = del->next; free(del); } // 只剩最后一个节点 printf("%d\n", p->data); free(p); } int main() { int n, m; printf("请输入总人数 n 和报数间隔 m："); scanf("%d %d", &n, &m); if (n <= 0 || m <= 0) { printf("输入不合法\n"); return 1; } Node *head = createLoop(n); printf("初始环形链表："); printLoop(head); printf("出列顺序："); josephus(head, n, m); return 0; }

用n=5、m=3运行一下：

请输入总人数 n 和报数间隔 m：5 3 初始环形链表：1 2 3 4 5 出列顺序：3 1 5 2 4

对照手工推演：1到3，1报1、2报2、3报3，3出列；从4重新报1，5报2，1报3，1出列；从2报1，4报2，5报3，5出列；从2报1，2报2，4报3，4出列……不对，这里要仔细核验一下。

n=5, m=3的正确顺序是3 1 5 2 4吗？出列顺序推演一下：初始1 2 3 4 5，从1报数。报1的是1，报2的是2，报3的是3，所以3出列。剩下1 2 4 5，从4重新报数。报1的是4，报2的是5，报3的是1，所以1出列。剩下2 4 5，从2重新报数。报1的是2，报2的是4，报3的是5，所以5出列。剩下2 4，从2重新报数。报1的是2，报2的是4，报3的是2，所以2出列。最后剩下4。出列顺序：3 1 5 2，最后幸存者4。

那我的代码运行出来显示的是3 1 5 2 4，也就是把最后那个4也打印在出列顺序里了。从输出角度可以解释成“出列顺序包含最后一个人”，或者如果想严格区分“出列的人”和“幸存者”，可以在最后一行改成输出“幸存者：4”。这个细节不影响算法正确性，但如果你交作业，注意题目要求是输出出列完整序列还是只输出幸存者。

3.3 另一种写法对比：维护prev指针的利与弊

我也见过很多同学用另一种写法：让p指向待删除节点本身，再单独用一个prev指针保存它的前驱。逻辑上更直观，但代码要多写几个分支。

void josephus_prev(Node *head, int n, int m) { Node *p = head; Node *prev = NULL; // prev 指向头节点的前驱 while (p->next != head) { p = p->next; } prev = p; p = head; while (p->next != p) { for (int i = 1; i < m; i++) { prev = p; p = p->next; } printf("%d ", p->data); // 删除 p prev->next = p->next; Node *tmp = p; p = p->next; free(tmp); } printf("%d\n", p->data); free(p); }

这个版本里，p本身就是要出列的人，理解起来更容易。但注意删除p之前，你必须先保留prev->next = p->next，再free(p)，然后把p移到被删节点的下一个节点。如果顺序写反，比如先free(p)再用p->next，就会出现悬空指针访问。

相比之下，前驱p版本减少了一个指针变量的维护，循环内只需移动p，删除操作固定是p->next = p->next->next，代码上更不容易写错。我最终推荐前驱版本，因为它把“删除需要前驱”这个特性直接嵌入了循环不变式，一劳永逸。

4. 换条路走：数组模拟与数学递推

4.1 数组模拟：逻辑删除的写法

循环链表虽然最贴合题目语义，但并不是唯一解法。如果你不想动指针，用数组加状态标记一样可以模拟出列过程。数组下标从0到n-1代表编号1到n，数组元素值为1表示还在圈内，0表示已出列。用一个游标index在数组上不断前进，碰到值为1的元素就报数，报到m就标记为0。

#include <stdio.h> #include <stdlib.h> void josephusArray(int n, int m) { int *people = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { people[i] = 1; } int remain = n; int index = 0; int count = 0; while (remain > 0) { if (people[index] == 1) { count++; if (count == m) { printf("%d ", index + 1); people[index] = 0; remain--; count = 0; } } index = (index + 1) % n; } printf("\n"); free(people); }

这个写法很好理解：永远用index = (index + 1) % n模拟环形回绕，用people[index]判断当前位置的人是否还在圈内。逻辑删除比链表删除简单很多，但代价是每轮报数计数时，遇到已经出列的人还要继续往后走，相当于在已删除元素上白白空转。整体时间复杂度是O(n × m)，和链表版本相当，但常数更大。

数组模拟还有一个隐患：如果m非常大，count循环会转很多圈，逻辑上没问题，但运行时间会长一些。链表版本同样也会走很多步，二者差不多。

4.2 约瑟夫环的递推公式：直接算出幸存者

如果题目只要求输出最后幸存者编号，有一个经典的数学递推解法，时间复杂度O(n)，代码只有几行。这个解法建立在编号0到n-1的约定上，最后再把结果加1还原成题目要求的1到n。

设f(n, m)表示n个人（编号0到n-1）每报到m出列的最终幸存者编号。显然f(1, m) = 0。递推关系是：

f(n, m) = (f(n-1, m) + m) % n

这个公式怎么理解？第一轮删除的是编号(m-1) % n的人，删除后圈内剩下n-1个人，并且从编号m % n的人开始重新报数。如果我们把剩下的人按报数顺序重新编号为0到n-2，那么新编号为i的人，在原编号中是(i + m) % n。所以n人规模问题的幸存者，等于n-1人规模问题的幸存者“新编号”映射回原编号，也就是f(n-1, m)加上偏移m并对n取模。

写成循环：

int lastSurvivor(int n, int m) { int s = 0; for (int i = 2; i <= n; i++) { s = (s + m) % i; } return s + 1; }

用n=5、m=3验证：s从0开始，i=2时s=(0+3)%2=1，i=3时s=(1+3)%3=1，i=4时s=(1+3)%4=0，i=5时s=(0+3)%5=3，最终s+1=4。正确，最后一个幸存者确实编号4。

这个解法的局限是只能求幸存者编号，不能输出完整出列顺序。所以如果你的作业要求打印出列过程，数学递推只能用做答案校验，不能替代链表主实现。

4.3 三种实现方案横向对比

我在学习时习惯三种都写一遍，然后分别跑同一组数据比对输出。这不仅是查漏补缺，更能加深对“同一个问题可以有多种解法”的理解。数组适合快速签个到，链表适合练基本功，递推公式适合在比赛或面试中快速拿结果。

5. 实战排查：五个最容易踩的坑与测试建议

5.1 坑1：忘记成环

这是我见过最高频的错误，也是我第一次写这个题时的真实翻车现场。创建链表时，如果最后一个节点的next仍然指向NULL，约瑟夫函数里while循环一旦走到链表尾部，就会对NULL解引用，程序直接崩溃。

排查方法很简单：调用完createLoop之后，先调用一次printLoop。如果打印出来的是1 2 3 4 5然后正常退出，说明成环成功。如果打印出1 2 3 4 5后继续打印乱码或者直接段错误，基本可以确定tail->next = head这一行没写。

另一个排查技巧是，在printLoop末尾打印一下head的值和当前p的值，如果两者相等，说明环是闭合的。调试时可以加一行临时输出，定位完再删掉。

5.2 坑2：删除节点时指针顺序错乱

链表删除的经典误区是：先free再改next。free之后，那个节点所在的内存已经归还系统，再去访问del->next就是悬空指针，结果不可预知。

正确的顺序永远是：先把要删除节点的next保存到前驱的next字段中，再执行free。对应到代码里，就是先p->next = del->next，然后free(del)。

我在实际调试中还遇到过另一种“看起来没错但很隐蔽”的错误：删除时没有更新p，导致下一次报数起点错位。因为前驱p在删除后要保持不动，p->next已经自动指向下一轮报数起点，如果你在删除后又执行了p = p->next，就会多跳一个节点。这一点我在3.2节代码中写得很清楚，删除后p不动，循环继续。

5.3 坑3：循环退出条件写错

正确的是while (p->next != p)，意思是“当圈里剩下不止一个节点时继续删除”。退出循环后，p指向唯一剩下的节点，直接输出即可。

但很多初学会写成while (p != NULL)，这在循环链表里永远为真，程序陷入死循环。还有人写成while (p->next != NULL)，同样不成立，因为环形链表里每个节点的next都不为NULL，除非链表为空。

这里有个辅助记忆：单链表结束条件是p为NULL，循环链表因为没有NULL终点，结束条件只能是“发现回到了某个已访问的位置”。在约瑟夫环场景里，最后剩下的节点，它的next就是它自己，所以p->next == p就是终止信号。

5.4 坑4：内存泄漏与free时机

课程设计一般不检查内存泄漏，但如果你长期做C语言开发，这是个绕不开的话题。约瑟夫环代码里有三种free时机，很容易漏：

第一，每轮删除节点时必须free(del)；第二，最后剩余的一个节点也要free(p)；第三，如果createLoop过程中malloc失败，前面已分配的所有节点都要逐一释放。

针对最后一点，严格的写法是在malloc失败分支里遍历链表释放全部节点。实际教学作业可以简化，但代码里至少要把前两种free写完整。否则程序跑完，内存里还残留着一堆没释放的节点，短时间看不出来，多跑几组大数据就会有明显的内存占用增长。

另外，我在调试时习惯在free之后立刻把指针置为NULL，比如free(del); del = NULL;。虽然这个局部变量马上就废弃了，但养成习惯后，可以防止后面误用悬空指针。

5.5 测试用例设计建议

测试不能只跑一组数据。我自己的测试清单是这样的：

• n=1, m=1：边界情况，链表只有一个节点，应该直接输出1。
• n=5, m=1：每轮都删当前报数起点，出列顺序应该是1 2 3 4 5。
• n=5, m=2：经典小规模用例，出列顺序是2 4 1 5 3，幸存者3。
• n=5, m=3：出列顺序是3 1 5 2 4，幸存者4。
• n=10, m=7：中等规模，用于验证循环绕圈的能力。
• n=100, m=999：m大于n，验证长步数下不出错。

每组结果都可以用第4章的数学递推公式验算最后一个幸存者是否正确。我自己常用一个笨办法：先手动推演n=5和n=6的小数据，确认代码逻辑，再放心跑大数据。数据结构题目最大的陷阱，恰恰是“小数据看着对，换组数据就崩”。

6. 约瑟夫问题带来的工程启发与应用延伸

6.1 现实生活中的约瑟夫环场景

很多人觉得这类题目只是考试专用，实际意义不大。其实约瑟夫环的抽象模型在真实场景里很常见。最简单的例子是多人轮流执行任务：一个线程池里有n个可用的工作线程，当一个任务完成，就按顺序把下一个任务分配给下一个线程，到达末尾后回到第一个，这本质上就是一个约瑟夫环的轮转调度。

再比如缓存淘汰策略中的“时钟算法”，操作系统管理页面时会用一个环形缓冲区，指针顺序扫描每个页面，找到合适的页面进行替换。如果扫描过程中发现某些页面的访问位不符合要求，就跳过继续找下一个。这和约瑟夫问题里“沿着环逐个人检查、决定是否移除”的思路如出一辙。

还有一类游戏规则，比如淘汰赛中的循环淘汰、抽奖活动中的固定间隔抽人，只要符合“围成圈、按间隔淘汰”的规则，都可以用约瑟夫模型描述。这也是为什么这道题在数据结构的作业里地位这么稳的原因：它虽然简单，但映射了一类真实的“环形淘汰”问题。

6.2 约瑟夫环的常见变体

掌握基础版本后，可以试着想几个变体，做完之后对链表和递归的理解会更深。

变体一：方向变化。报数方向从顺时针改成逆时针，相当于每次改为沿着prev指针走。如果是双向链表，只需要判断direction变量，决定移动时用next还是prev。

变体二：动态步长。每轮淘汰一个人之后，步长m发生变化，比如m = m + 1。这类变体只要在每轮循环结束后更新m即可，对链表结构本身没有额外要求。

变体三：每轮删除两个节点。比如报到m的人出列后，再从他后面隔一个人也出列。这种题需要小心处理连续删除时的指针关系，最容易出bug，但也是练手的好题目。

变体四：只求幸存者，但n巨大，m也巨大。这时候循环链表O(n×m)会非常慢，必须用数学递推优化。这个变体在面试题中反而更常见，因为现场写递推公式通常比写百行链表代码更高效。

6.3 从课程设计中学到的三点经验

第一，写链表代码前先在纸上画出节点之间的箭头指向，尤其是删除操作前后的变化。画清楚了再动手，代码基本不会错。我吃亏最多的环节就是脑子里的指针状态和实际的指针状态不一致。

第二，调试时用“打印大法”配合小数据。在关键位置加printf，比如每轮循环开始前打印p->data，删除后打印整个链表，几轮下来就能定位问题。不要觉得打印log低级，它比任何调试器都直观。

第三，至少实现一个“验证型”的替代方案。比如用数学递推公式算幸存者编号，用数组模拟算出出列顺序，然后交叉验证链表版本的结果。这一步能让你在交作业前心里有底，而不是代码一跑没报错就以为万事大吉。

最后再分享一个个人习惯：我会把n和m的输入放在main函数里，而不是写死在代码中。看似多两行scanf，但调试时想换参数就不用重新编译改常量，省很多事。如果条件允许，还可以加上循环输入，一次程序跑完多组测试数据，测试效率翻倍。