用c++链表实现约瑟夫环

好的，以下是使用C++链表实现约瑟夫环的示例代码：

#include <iostream>
using namespace std;

// 定义节点结构体
struct Node {
    int num; // 节点编号
    Node *next; // 指向下一个节点的指针
};

// 创建链表
Node* createList(int n) {
    Node *head = new Node(); // 创建头节点
    head->num = 1;
    head->next = NULL;

    Node *cur = head;
    for (int i = 2; i <= n; i++) {
        Node *newNode = new Node();
        newNode->num = i;
        newNode->next = NULL;

        cur->next = newNode;
        cur = newNode;
    }

    cur->next = head; // 链接成环形链表

    return head;
}

// 删除第m个节点
void deleteNode(Node *&head, int m) {
    Node *cur = head;
    Node *prev = NULL;

    // 找到第m个节点和它前一个节点
    while (cur->num != m) {
        prev = cur;
        cur = cur->next;
    }

    // 删除第m个节点
    if (prev == NULL) { // 删除头节点
        head = cur->next;
    } else {
        prev->next = cur->next;
    }
    delete cur;
}

// 约瑟夫环
void josephus(int n, int m) {
    Node *head = createList(n);

    Node *cur = head;
    while (cur->next != cur) { // 当只剩下一个节点时退出循环
        // 找到第m个节点
        for (int i = 1; i < m; i++) {
            cur = cur->next;
        }

        // 删除第m个节点
        int num = cur->num;
        deleteNode(head, num);

        cur = cur->next; // 继续从下一个节点开始找
    }

    // 输出最后剩下的节点编号
    cout << "Last node: " << cur->num << endl;

    // 释放链表内存
    delete cur;
}

int main() {
    int n, m;
    cout << "Enter n and m: ";
    cin >> n >> m;

    josephus(n, m);

    return 0;
}

该实现方式中，首先创建一个包含n个节点的环形链表，然后从头节点开始，每次找到第m个节点并删除它，直到链表只剩下一个节点为止。最后输出剩下的节点编号。