什么是循环链表？如何用它解决约瑟夫环问题？

简化版

循环链表是尾节点的 next 指回头节点、首尾相接成环的链表，从任意节点出发都能绕回原点。约瑟夫环问题（n 人围圈报数、每数到 m 就出局，问最后剩谁）用循环链表可直接模拟：建一个 n 节点的环，每数 m 个就删一个节点，直到只剩一个。也可以用数学递推公式 f(n) = (f(n-1) + m) % n O(n) 求解。

详细版

循环链表：普通链表尾节点 next 为 null，循环链表让尾节点 next 指回头，形成环。分单向循环、双向循环。特点是没有「末尾」，从任一点出发沿 next 走会无限循环，适合表示「环形」的场景（轮询调度、约瑟夫环、循环缓冲）。

约瑟夫环：n 个人编号 0 ~ n-1 围成一圈，从某人开始报数，报到第 m 个的人出局，然后从下一个人重新报数，如此循环，求最后幸存者的编号。

解法一：循环链表模拟

int josephus(int n, int m) {
    // 建循环链表 0..n-1
    Node head = new Node(0), cur = head;
    for (int i = 1; i < n; i++) { cur.next = new Node(i); cur = cur.next; }
    cur.next = head;                     // 首尾相接成环
    Node prev = cur;                     // prev 是 head 的前驱
    while (head.next != head) {          // 剩多于 1 个
        for (int i = 1; i < m; i++) {    // 走 m-1 步，head 停在要删的节点
            prev = head; head = head.next;
        }
        prev.next = head.next;           // 删除 head
        head = head.next;                // 从下一个继续
    }
    return head.val;
}

时间 O(n·m)，直观易懂。

解法二：数学递推（约瑟夫递推式）

int josephus(int n, int m) {
    int pos = 0;                         // 只剩 1 人时，其编号为 0
    for (int i = 2; i <= n; i++)
        pos = (pos + m) % i;             // 逆推回 n 人时的编号
    return pos;
}

时间 O(n)、空间 O(1)，是最优解。

完整版教学

一、循环链表的特点与用途

普通链表有明确的「头」和「尾」（尾的 next 是 null）。循环链表把尾接回头，于是：

没有尽头：遍历要用「回到起点」而非「next 为 null」作为终止条件，否则死循环。
从任意节点可达全部：适合表示环形关系。
典型应用：轮询调度（CPU 时间片轮转 RR）、约瑟夫环、环形缓冲区的链表版、音乐循环播放列表。

遍历循环链表的终止条件常写成 do { ... } while (cur != head)，用「是否绕回头节点」判断是否走完一圈。

二、约瑟夫环用循环链表模拟

约瑟夫环天然就是「一圈人循环报数、出局」，和循环链表结构完全对应：

建 n 个节点的循环链表代表 n 个人。
从起点走 m-1 步（报数报到第 m 个），删掉那个节点（这个人出局）。
从被删节点的下一个继续，重复，直到环里只剩一个节点。

模拟法直观、好理解，但每删一人要走 m 步，总时间 O(n·m)，n、m 很大时偏慢。

三、数学递推法为什么成立

设 f(n, m) 是「n 个人时幸存者的编号」（从 0 开始编号）。关键观察：每淘汰一个人，问题就规模减一，但幸存者在新旧编号里的位置有固定偏移。

只剩 1 人时，幸存者编号显然是 0，即 f(1) = 0。
从 n-1 人推到 n 人：淘汰掉第一个出局者后，剩下的人重新构成一个 n-1 人的子问题，但整体编号被「往前挪了 m」。所以逆映射回来是：

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

从 f(1)=0 一路递推到 f(n)，就得到 n 人时的幸存者编号。O(n) 时间，远优于模拟。

注意报数从 1 开始、编号从 0 开始时用 (f(n-1)+m) % n；如果题目要求编号从 1 开始，最后结果 +1。

四、两种解法怎么选

要求还原过程 / n、m 不大 / 面试考链表操作 → 循环链表模拟，直观且能展示链表功底。
只要最终答案 / n 很大 → 数学递推 O(n)，最优。
用数组或队列同样能模拟（队列：出队报数、报到 m 的丢弃、其余重新入队），思路等价。

五、易错点

建环后遍历终止条件要用「回到起点」，不能等 next 为 null（永远不为 null）。
模拟删除时注意维护前驱指针，才能 O(1) 摘除节点。
递推式的取模和编号起点（0 还是 1）要对齐，容易差一。

六、常见误区与追问

问题形态	推荐解法	复杂度
要展示出局过程	循环链表模拟	O(n·m)
只问最后幸存者	数学递推	O(n)
编号从 1 开始	递推结果最后 `+1`	O(n)

易错点：循环链表没有 null 终点，遍历和删除都必须明确“什么时候绕回起点”或“什么时候只剩一个节点”。

用 n=5,m=3 推一遍 0 基编号递推：f(1)=0；f(2)=(0+3)%2=1；f(3)=(1+3)%3=1；f(4)=(1+3)%4=0；f(5)=(0+3)%5=3。所以 0 基幸存者是 3，如果题目编号从 1 开始，答案就是 4。这个例子也能帮助检查取模和编号是否对齐。

误区：循环链表遍历还能用 cur != null 结束。 尾节点会指回头节点，cur 不会自然变成 null，必须用回到起点或剩余节点数控制。
误区：约瑟夫递推式不需要关心编号起点。 f(n)=(f(n-1)+m)%n 是 0 基编号，1 基输出通常要最后加 1。
误区：循环链表模拟一定是最优解。 模拟适合展示过程；只求结果时数学递推 O(n) 更优。
追问：为什么模拟删除要维护前驱？ 单链表删除当前节点需要前驱改 next，否则无法 O(1) 摘除节点。
追问：m 很大时模拟为什么慢？ 每淘汰一个人都要走 m-1 步，整体可能达到 O(n·m)。
追问：递推式为什么是加 m 再取模？ 从 n-1 人子问题映射回 n 人原编号时，幸存者位置整体偏移了 m 个位置，再用 % n 回到环上。

七、加强记忆

循环链表 = 尾节点 next 指回头、首尾成环，没有尽头，遍历以「绕回起点」为终止条件，适合轮询、约瑟夫环等环形场景。约瑟夫环两解法：循环链表模拟（每走 m 步删一个，O(n·m)，直观）；数学递推 f(n)=(f(n-1)+m)%n（从 f(1)=0 推到 n，O(n)，最优）。注意编号起点与报数起点对齐。

简化版

详细版