循环链表完成约瑟夫问题 c++

约瑟夫问题是一个经典的算法问题，通常涉及到在一个循环链表中，从头开始按顺序计数，每到某个指定数字k（通常是除了链表长度之外的最大公约数），就删除当前节点并继续计数。这个过程会一直持续直到链表中只剩下一个节点为止。

在C++中，可以这样实现一个循环链表并解决约瑟夫问题：

#include <vector>
using namespace std;

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

Node* createCycleList(int n, int k) {
    // 创建一个n节点的循环链表
    vector<Node*> nodes(n);
    for (int i = 0; i < n; ++i) {
        nodes[i] = new Node{i};
        if (i != 0)
            nodes[i - 1]->next = &nodes[i];
        else
            nodes[n - 1]->next = nodes[0]; // 创建循环
    }
    return nodes[0];
}

void josephusProblem(Node* head, int k) {
    if (!head || !head->next)
        return; // 空链表或只有一个节点

    Node* slow = head;
    Node* fast = head;

    // 找到链表的长度，因为快指针每次移动k步，慢指针每次一步
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 当快指针到达链表的最后一个节点时，慢指针正好指向删除节点后的第一个节点
    slow = head;
    for (int i = 1; i <= k - 1; ++i)
        slow = slow->next;

    // 删除节点并返回新头结点
    delete slow;
    return josephusProblem(head->next, k); // 递归删除并更新头节点
}

int main() {
    int n, k;
    cin >> n >> k;
    Node* listHead = createCycleList(n, k);
    cout << "Josephus Problem solution: ";
    josephusProblem(listHead, k);
    return 0;
}

在这个代码中，首先创建了一个循环链表，然后通过快慢指针找到起始删除位置，接着按照约瑟夫环的规则逐次删除节点，直至剩余一个节点。