用C++的循环链表实现约瑟夫环游戏

约瑟夫环游戏是一个经典的算法问题，它通常涉及到一个圈形的数组，玩家按照特定的规则跳过元素并删除它们。在C++中，我们可以使用循环链表（Circular Doubly Linked List）来实现，因为它支持高效的插入和删除操作。

首先，我们需要创建一个节点结构，包含数据和指向前后节点的指针：

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

然后，我们建立一个循环链表，并设置一个计数器`current`表示当前轮到谁：

Node* head = nullptr; // 空链表
int current = 0;

// 初始化函数
void init(int size) {
    Node* newNode = new Node{0, nullptr, nullptr};
    for (int i = 1; i < size; ++i) {
        newNode->next = new Node{i, newNode, nullptr};
        newNode->prev = newNode->next->prev;
        if (head == nullptr)
            head = newNode;
        else
            head->next->prev = newNode;
    }
    newNode->next = head; // 创建循环
    current = size - 1; // 设置初始位置
}

游戏的主要逻辑是这样的：

void josephusGame(int k) {
    while (head != nullptr) {
        current = (current + k - 1) % nodesCount(); // k步后的位置
        delete head->data; // 删除该位置的节点
        if (head == current) { // 如果头节点就是下一个淘汰者
            head = nullptr; // 游戏结束，链表为空
        } else {
            head = head->next; // 更新头节点
        }
    }
}

其中`nodesCount()`是获取链表中节点数量的辅助函数：

int nodesCount() {
    Node* temp = head;
    int count = 0;
    do {
        count++;
        temp = temp->next;
    } while (temp != head);
    return count;
}