用c++语言链表方式写约瑟夫环

在C++中，我们可以使用链表数据结构实现约瑟夫环（Josephus Problem）。约瑟夫环是一个经典问题，描述的是在一个循环数组中，每隔k步删除一个元素，直到剩下最后一个元素。以下是使用链表实现的一个简单示例：

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node* next;
};

// 创建一个新的节点
Node* createNode(int val) {
    Node* newNode = new Node();
    newNode->value = val;
    newNode->next = nullptr;
    return newNode;
}

// 约瑟夫环函数
void josephus(Node** head, int k) {
    if (*head == nullptr || k <= 1) {
        cout << "Invalid input" << endl;
        return;
    }

    Node* lastNonDeleted = *head;
    Node* runner = *head->next;

    for (int i = 2; ; ++i) {
        // 删除第k个节点
        runner = runner->next;
        if (!runner || runner == *head) {
            // 如果到达链表结束或又回到起点，lastNonDeleted就是结果
            cout << "Last remaining node is: " << lastNonDeleted->value << endl;
            break;
        }
        if (i % k == 0) {
            // 如果当前轮到删除
            delete runner;
            runner = runner->next;
        } else {
            // 否则，更新lastNonDeleted和runner
            lastNonDeleted = runner;
        }
    }
}

int main() {
    // 初始化链表，例如有5个节点，每4个节点删除一个
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    josephus(&head, 4);  // 调用约瑟夫环函数

    return 0;
}

在这个例子中，`josephus`函数接受头节点的指针和步长k作为参数，通过遍历链表并删除指定位置的节点，最后输出剩余的最后一个节点。