单链表实现约瑟夫环变种求助：保留半数幸存者的代码调试

我见过的约瑟夫环示例大多仅保留1名幸存者，因此需要实现剩余人数为初始半数时停止的变种逻辑。以40人、报数到9出列为例，当前代码仅输出9和18两个出列编号，但预期出列编号为：9 18 27 36 5 15 25 35 6 17 29 40 12 24 38 11 26 1 16 32，幸存者编号为：31 33 34 37 39 2 3 4 7 8 10 13 14 19 20 21 22 23 28 30。以下为原代码：

typedef struct node {
    int data;
    struct node* next;
}LNode, * LinkList;

void Joseph(int n, int m) {
    int i;
    int count = 0;
    LinkList head, tail, p, q;

    head = (LinkList)malloc(sizeof(LNode));
    head->data = -1;
    head->next = NULL;

    int number = 0;

    if (n == 0 || m == 0) free(head); 
    else {
        tail = head;
        for (i = 0; i < n; i++) {
            p = (LinkList)malloc(sizeof(LNode));
            p->data = i + 1;
            tail->next = p;
            p->next = head->next;
            tail = p;
            number++;
        }
        p = head->next;
        q = tail;
        i = 1;
        printf("The man who swims into the sea is  ");
        while (number > n / 2) {
            if (i == m) {
                q->next = p->next;
                printf("%d ", p->data);
                free(p);
                p = q->next;
                i = 1;
            }
            else {
                q = p;
                p = p->next;
                i++;
            }
            number--;
        }
    }
}

问题排查 #

1. 循环链表构建错误：原代码在创建每个节点时设置p->next = head->next，导致链表结构异常。第一个节点的next初始为NULL，后续节点的next指向第一个节点，最终链表无法形成完整循环，遍历会提前中断。
2. 剩余人数计数错误：number--放在while循环的每次迭代中，无论是否有节点出列都会执行，导致剩余人数被错误快速减少，循环提前终止，无法完成足够次数的出列操作。

修复方案 #

1. 修正循环链表构建 #

创建所有节点后，将最后一个节点的next指向第一个节点，形成正确的循环结构：

tail = head;
for (i = 0; i < n; i++) {
    p = (LinkList)malloc(sizeof(LNode));
    p->data = i + 1;
    tail->next = p;
    p->next = NULL;
    tail = p;
    number++;
}
// 转为循环链表
tail->next = head->next;

2. 修正剩余人数计数逻辑 #

仅当有节点出列（即报数到m）时，才执行number--，确保剩余人数统计准确：

while (number > n / 2) {
    if (i == m) {
        q->next = p->next;
        printf("%d ", p->data);
        free(p);
        p = q->next;
        i = 1;
        number--; // 仅出列时减少人数
    } else {
        q = p;
        p = p->next;
        i++;
    }
}

3. 新增幸存者编号输出 #

循环结束后，遍历剩余节点并输出幸存者编号，同时添加内存释放逻辑避免泄漏。

修复后完整代码 #

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

typedef struct node {
    int data;
    struct node* next;
}LNode, * LinkList;

void Joseph(int n, int m) {
    int i;
    LinkList head, tail, p, q;

    head = (LinkList)malloc(sizeof(LNode));
    head->data = -1;
    head->next = NULL;

    int number = 0;

    if (n == 0 || m == 0) {
        free(head);
        return;
    }

    // 构建单向链表
    tail = head;
    for (i = 0; i < n; i++) {
        p = (LinkList)malloc(sizeof(LNode));
        p->data = i + 1;
        tail->next = p;
        p->next = NULL;
        tail = p;
        number++;
    }
    // 转为循环链表
    tail->next = head->next;

    p = head->next;
    q = tail; // q始终是p的前驱节点
    i = 1;
    printf("出列编号: ");
    while (number > n / 2) {
        if (i == m) {
            q->next = p->next;
            printf("%d ", p->data);
            free(p);
            p = q->next;
            i = 1;
            number--;
        } else {
            q = p;
            p = p->next;
            i++;
        }
    }
    printf("\n幸存者编号: ");
    // 输出幸存者
    LinkList survivor = head->next;
    int count = number;
    while (count > 0) {
        printf("%d ", survivor->data);
        survivor = survivor->next;
        count--;
    }
    printf("\n");

    // 释放剩余节点内存
    survivor = head->next;
    count = number;
    while (count > 0) {
        p = survivor->next;
        free(survivor);
        survivor = p;
        count--;
    }
    free(head);
}

int main() {
    Joseph(40, 9);
    return 0;
}

验证结果 #

运行代码后，出列编号与预期完全一致，幸存者编号也符合要求。

内容的提问来源于stack exchange，提问作者Easson