josephus · 循环链表经典应用

约瑟夫环：模拟 / 递推 / 闭式解

$n$ 个人围成一圈，编号 0 ~ n-1，从 #0 起报数，每数到第 $k$ 个就把他移出圈子，再从下一人重新报数，直到只剩一人——问最后幸存者的编号。传说历史学家 Flavius Josephus 与 40 名同伴（共 41 人）被困，约定按此规则轮流自尽，他算出了最后存活的位置而得以活命。这道题常用来考察循环链表与**「问题规模缩减 + 编号映射」**这类递推建模。下面把三条解法做成对等的可视 lab，切换观察同一答案如何被算出：模拟在循环链表上逐个报数删除，直观但 $O(n\cdot k)$ ;递推用 f(n) = (f(n-1)+k) mod n 把答案从小问题映射回原编号， $O(n)$ 、 $O(1)$ 空间；闭式解 仅当 k = 2 时存在，把 $n$ 的二进制最高位移到末尾即得， $O(1)$ 。三法都以 0-indexed 输出，可相互印证（k=2 时递推 f(n) 恰等于闭式解的 2l）。

图 1 · 约瑟夫环的三条解法对照：循环链表模拟、递推与位运算闭式解，可切换观察同一答案如何被算出。

为什么递推式是 f(n) = (f(n-1)+k) mod n?淘汰第一个人（编号 k-1）后，剩下 n-1 人构成一个规模更小的同类子问题，但报数的新起点变成了编号 $k$ 的人。若把这个新起点重新编号为 0，子问题的答案就是 f(n-1)；再把它映射回原始编号——整体加上偏移 $k$ 、对 $n$ 取模绕回圈内，即 (f(n-1)+k) mod n。基例 f(1)=0：只剩一人时幸存者就是他自己。一趟循环从 f(1) 推到 f(n)，无需真正维护链表， $O(n)$ 时间、 $O(1)$ 空间。

k = 2 的闭式解：最高位「绕」到最低位。把 $n$ 写成 2^m + l（2^m 是不超过 $n$ 的最大 2 的幂， $l = n - 2^m$ ），则 1-indexed 的幸存者编号为 2l + 1。换成二进制，正是把 $n$ 的最高位那个 1 拿掉、其余整体左移一位、末尾补 1——例如 ${41 = 101001_2}$ ，旋转后得 ${010011_2 = 19}$ ，即第 19 位幸存（0-indexed 为 2l = 18）。这与递推法在 k=2 时给出的 f(n) 完全一致，可在上面切换两种解法对照。

**三条解法的取舍。**模拟最贴近题意、能看清每一步淘汰，但每淘汰一人都要走 $k$ 步，总计 $O(n\cdot k)$ , $n$ 大时偏慢——它真正的价值是把循环链表删除演示得直观。递推是工程上的最优通用解：任意 $k$ 都适用， $O(n)$ 时间、 $O(1)$ 空间。闭式解最快（ $O(1)$ 次字长位运算）却只覆盖 $k = 2$ 这一特例。约瑟夫环正是「同一问题、解法可层层优化」的典型：从能跑、到够快、再到针对特例的常数时间。