4. 循环链表的约瑟夫环模拟

约瑟夫环的链表模型

约瑟夫环问题可以描述为：n 个人围成一圈，从第 1 个人开始报数，每报到第 m 个人就出列，然后从下一个人重新从 1 开始报数，直到所有人出列。用循环链表模拟时，每个节点代表一个人，节点的 next 指针始终指向环中的下一个存活节点。核心操作有两个：报数推进（沿 next 移动 m-1 次）和节点删除（让前驱节点的 next 跳过被删除节点）。

循环链表节点定义与建环

每个节点包含数据域和指针域。建环时先创建 n 个节点并依次链接，最后将尾节点的 next 指回头节点，形成闭环。头指针 head 指向第 1 个节点，同时用 tail 记录尾节点以便快速完成闭环。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int id;                 /* 编号 1..n */
    struct Node *next;
} Node;

/* 创建 n 个节点的循环链表，返回头指针 */
Node *createCircle(int n) {
    if (n <= 0) return NULL;
    Node *head = (Node *)malloc(sizeof(Node));
    head->id = 1;
    head->next = head;      /* 先自环，便于统一处理 */
    Node *tail = head;
    for (int i = 2; i <= n; i++) {
        Node *p = (Node *)malloc(sizeof(Node));
        p->id = i;
        p->next = head;     /* 新节点指向头，保持环 */
        tail->next = p;     /* 旧尾指向新节点 */
        tail = p;           /* 更新尾 */
    }
    return head;
}

约瑟夫环模拟函数

模拟过程维护两个指针：prev 指向当前报数起点的前驱，curr 指向当前报数起点。每轮先让 curr 沿环前进 m-1 步（prev 同步跟随），此时 curr 就是出列者。删除时执行 prev->next = curr->next，然后释放 curr，并将 curr 重置为 prev->next 作为下一轮起点。当环中只剩一个节点时（curr->next == curr），该节点即为幸存者。

/* 返回最后幸存者的编号 */
int josephus(int n, int m) {
    if (n <= 0 || m <= 0) return -1;
    Node *head = createCircle(n);
    Node *prev = head;
    while (prev->next != head) prev = prev->next;  /* prev 指向尾节点 */
    Node *curr = head;

    while (curr->next != curr) {          /* 环中多于 1 个节点 */
        for (int i = 1; i < m; i++) {     /* 报数 m-1 次 */
            prev = curr;
            curr = curr->next;
        }
        printf("出列: %d\n", curr->id);
        prev->next = curr->next;          /* 跳过 curr，维护环 */
        free(curr);
        curr = prev->next;                /* 下一轮从下一个人开始 */
    }
    int survivor = curr->id;
    free(curr);
    return survivor;
}

int main(void) {
    int n = 7, m = 3;
    int s = josephus(n, m);
    printf("n=%d, m=%d 的幸存者: %d\n", n, m, s);
    return 0;
}

运行结果与验证

以 n=7、m=3 为例，程序输出如下（与上方 SVG 中的出列顺序一致）：

出列: 3
出列: 6
出列: 2
出列: 7
出列: 5
出列: 1
n=7, m=3 的幸存者: 4