循环链表与约瑟夫环：一个古老问题的现代解法

约瑟夫环的故事：罗马军队被围，n 名将士决定宁死不降，围成一圈，从某人起每数到第 m 人就杀掉，直到最后一人自尽。约瑟夫斯算出自己该站哪才活下来——这道题从此以他的名字命名。

为什么用循环链表？人"围成一圈"这个设定，天然就是循环链表：尾节点的 next 指回头节点。每数 m 下，就沿 next 走 m-1 步，然后删除当前节点（双向或单链都可 O(1) 摘除已知节点），被删节点的后继成为新的当前点，继续数，直到链上只剩一个节点。

代码骨架（单循环链表）：

这题的妙处在于：它既是历史趣闻，又是检验"链表删除 + 循环终止"基本功的绝佳练习。更进阶的版本可以用数学递推直接算出幸存者位置（O(n) 而非模拟），但理解循环链表的模拟，是迈出第一步的关键。

今天我们从 C3 节点把循环链表讲透，约瑟夫环就是它最富戏剧性的"用户案例"。

图：n 人围成一圈，循环链表天然建模

参考代码（Python）

人围成一圈天然是循环链表，下面用循环链表模拟约瑟夫环。

class Node:
    def __init__(self, v): self.v=v; self.next=None

def josephus(n, m):
    head=Node(1); cur=head
    for i in range(2, n+1):
        cur.next=Node(i); cur=cur.next
    cur.next=head            # 尾连头 → 循环链表
    while cur.next != cur:   # 剩一个时停止
        for _ in range(m-1): cur=cur.next
        cur.next=cur.next.next   # 删除下一节点
    return cur.v

关联推荐

• 算法与问题求解入门 — 建模问题的能力，比背答案更重要
• 二分查找 — 另一个"把朴素 O(n) 压到 O(log n)"的思路
• 算法通关训练营·入门篇 — 系统建立算法直觉