约瑟夫环循环链表C语言实现

下面是使用循环链表实现约瑟夫环的 C 语言代码：

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

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

Node* createList(int n) {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* p = head;
    for (int i = 1; i <= n; i++) {
        Node* node = (Node*)malloc(sizeof(Node));
        node->data = i;
        p->next = node;
        p = node;
    }
    p->next = head->next;
    free(head);
    return p->next;
}

int josephus(int n, int k) {
    Node* head = createList(n);
    Node* p = head;
    while (p->next != p) {
        for (int i = 1; i < k; i++) {
            p = p->next;
        }
        Node* temp = p->next;
        p->next = temp->next;
        printf("%d ", temp->data);
        free(temp);
    }
    int survivor = p->data;
    free(p);
    return survivor;
}

int main() {
    int n, k;
    printf("请输入总人数n和报数k：\n");
    scanf("%d %d", &n, &k);
    int survivor = josephus(n, k);
    printf("\n最后生还者的编号为：%d\n", survivor);
    return 0;
}

首先，我们先创建一个循环链表，然后依次删除每个第 k 个节点，直到链表中只剩下一个节点为止。在每次删除节点时，我们需要记录下被删除节点的编号，最后留下的节点即为最后一个生还者，返回其编号即可。