用c语言循环单链表解决约瑟夫问题

约瑟夫环问题是一个经典的算法问题，它描述的是在一个环形队列中，每个人按照顺序报数，每次跳过一个人，直到只剩下最后一个人。我们可以用C语言的循环单链表来模拟这个问题。以下是一个简单的解决方案：

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

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

void initializeList(Node** head) {
    *head = NULL;
}

void insertNode(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

int josephusProblem(int n, int k) {
    if (n == 1 || k >= n) {
        printf("Josephus problem has no solution for given input.\n");
        return -1; // 或者返回第一个数字作为结果
    }

    Node* tail = *head;
    while (--n > 0) {
        tail = tail->next;
    }
    int current = *head;
    
    while (1) {
        printf("%d ", current->data); // 输出当前节点值
        current = current->next;
        if (current == tail) { // 当轮到最后一个节点时，开始下一轮
            tail = *head;
            current = current->next;
        }
        if (current == (*head)) { // 如果轮到了头节点，则退出循环，因为头节点已经遍历了k次
            break;
        }
    }
    return current->data;
}

int main() {
    Node* head = NULL;
    initializeList(&head);
    // 插入节点...
    int n = 5, k = 3; // 假设有5个人，每次跳过3人
    josephusProblem(n, k);
    return 0;
}

在这个例子中，我们首先创建一个空链表`head`，然后插入节点代表人们。`josephusProblem`函数通过迭代计算并打印出被淘汰的人，直到剩下最后一个人。