C语言循环链表实现约瑟夫问题：find_last函数错误排查求助

现有代码核心问题分析 #

1. 链表创建函数未形成循环链表 #

create_list函数的最大问题是没有将链表闭环为循环链表，约瑟夫问题依赖循环遍历，原代码的链表尾节点next为NULL，遍历到末尾会中断，这是后续find_last逻辑失效的根本原因之一。

2. 初始版find_last的错误 #

• 逻辑完全偏离：通过j匹配节点的number值来计数，这和约瑟夫问题“按顺序计数淘汰”的核心逻辑不符；
• 循环条件错误：用current->next != NULL判断终止，不适合循环链表；
• 计数重置错误：删除节点后将j重置为1，破坏了连续计数的逻辑。

3. 修改版find_last的错误 #

• 删除节点代码逻辑错误：delete->next = current->next;完全颠倒了指针指向，正确操作应该是让前驱节点跳过待删节点；
• 循环条件错误：while(i != N)会尝试删除N个节点，但总节点数只有N个，最后会导致空指针访问；
• 计数逻辑缺失：删除节点后未正确更新计数起点，后续计数会出现偏移；
• 未适配循环链表的遍历逻辑。

完整修复方案 #

步骤1：修复create_list，创建真正的循环链表 #

修改链表创建逻辑，确保尾节点指向头节点，形成闭环：

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

typedef struct node {
    int number;
    struct node* next;
} Node;

void create_list(int N, Node* head){
    Node* tail = head; // 跟踪尾节点
    for(int i = 2; i <= N; i++){
        Node* tmp_node = (Node*)malloc(sizeof(Node));
        tmp_node->number = i;
        tmp_node->next = NULL;
        tail->next = tmp_node;
        tail = tmp_node;
    }
    tail->next = head; // 尾节点指向头节点，形成循环链表
}

步骤2：重写find_last函数，实现正确的约瑟夫淘汰逻辑 #

核心逻辑：从尾节点开始（方便定位待删节点的前驱），每次计数M次，删除第M个节点，重复直到只剩一个节点：

int find_last(int M, int N, Node* head){
    if(N == 1){ // 边界情况：只有一个节点直接返回
        return head->number;
    }

    Node* current = head;
    // 先移动到尾节点（current->next 即为头节点）
    while(current->next != head){
        current = current->next;
    }

    // 淘汰N-1个节点，保留最后一个
    for(int i = 0; i < N-1; i++){
        // 计数M次，移动到待删节点的前驱
        for(int j = 1; j < M; j++){
            current = current->next;
        }
        // 删除current的下一个节点
        Node* delete_node = current->next;
        current->next = delete_node->next;
        free(delete_node);
    }

    return current->next->number;
}

步骤3：修正main函数的调用 #

更新find_last的调用参数，同时补充缺失的read_numbers函数：

void read_numbers(int* N, int* M){
    printf("请输入总人数N和步长M：");
    scanf("%d %d", N, M);
}

int main(){
    int M, N, res;
    Node* head = (Node*)malloc(sizeof(Node));
    head->number = 1;
    head->next = NULL;
    
    read_numbers(&N, &M);
    create_list(N, head);
    res = find_last(M, N, head);
    printf("最后剩余的元素是：%d\n", res);

    // 释放最后剩余的节点，避免内存泄漏
    free(head);
    return 0;
}

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