约瑟夫环问题：用 C 语言实现单向循环链表解法

约瑟夫环问题是一个经典的算法问题，它描述了这样一个场景：罗马人占领乔塔帕特后，犹太人与 Josephus 及他的朋友躲到一个洞中，族人决定宁愿死也不要被敌人找到，于是决定了一个自杀方式，所有人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而 Josephus 和他的朋友并不想死，Josephus 要他的朋友先假装遵从，他将朋友与自己安排在两个特殊的位置，于是逃过了这场死亡游戏。

现在假设有 n 个人形成一个单向循环链表，用 C 语言求最后剩余的两个节点。

我们可以使用单向循环链表来表示这个问题。首先，我们需要定义一个节点的结构：

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

然后，我们可以编写一个函数来创建一个大小为 n 的单向循环链表：

Node* createCircularLinkedList(int n) {
    Node* head = NULL;
    Node* prev = 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;
        } else {
            prev->next = newNode;
        }

        prev = newNode;
    }

    prev->next = head;  // make the list circular

    return head;
}

接下来，我们可以编写一个函数来解决该问题，该函数接受一个单向循环链表的头节点和要保留的最后两个节点的指针作为参数：

void josephusProblem(Node* head, Node** survivor1, Node** survivor2) {
    Node* current = head;
    Node* prev = NULL;

    while (current->next != current) {
        // Skip two nodes
        prev = current;
        current = current->next;
        prev->next = current->next;

        // Move to the next node
        current = prev->next;
    }

    *survivor1 = current;
    *survivor2 = current->next;
}

最后，我们可以在主函数中使用这些函数来解决该问题：

int main() {
    int n;
    printf("Enter the number of people: ");
    scanf("%d", &n);

    // Create the circular linked list
    Node* head = createCircularLinkedList(n);

    // Solve the Josephus problem
    Node* survivor1;
    Node* survivor2;
    josephusProblem(head, &survivor1, &survivor2);

    // Print the survivors
    printf("Survivor 1: %d\n", survivor1->data);
    printf("Survivor 2: %d\n", survivor2->data);

    // Free the memory
    free(head);

    return 0;
}

这样，我们就可以得到最后剩余的两个节点的值。