C语言中怎样实现约瑟夫环 C语言循环链表解决经典问题

next

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createCircularList(int n) {
    Node* head = NULL;
    Node* tail = NULL;

    for (int i = 1; i <= n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = i;
        newNode->next = NULL;

        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    tail->next = head; // 形成循环
    return head;
}

int josephus(int n, int k) {
    Node* head = createCircularList(n);
    Node* current = head;
    Node* prev = NULL;

    while (current->next != current) { // 循环直到只剩一个节点
        for (int i = 1; i < k; i++) { // 报数 k-1 次
            prev = current;
            current = current->next;
        }

        // 移除 current 节点
        prev->next = current->next;
        Node* temp = current;
        current = current->next;
        free(temp);
    }

    int result = current->data;
    free(current); // 释放最后一个节点
    return result;
}

n

k

k