用头插法建立循环链表解决约瑟夫问题

约瑟夫问题是一个经典的数学问题，假设有n个人围成一圈，从第一个人开始报数，数到m的人出圈，然后从出圈的人的下一个人开始重新报数，数到m的人再次出圈，直到所有人都出圈为止。现在我们可以用头插法建立循环链表来解决这个问题。

首先，我们可以用一个循环链表来表示这n个人。我们可以把每个人看作一个节点，节点中保存着这个人的编号和指向下一个节点的指针。

接下来，我们可以用头插法建立这个循环链表。具体地，我们可以从最后一个人开始，一个一个地向链表中插入节点。每次插入一个节点，我们都把它插入到链表的头部，也就是让它成为链表的第一个节点。这样，最后形成的循环链表就是按照从最后一个人到第一个人的顺序排列的。

最后，我们可以采用模拟的方式来解决约瑟夫问题。我们从链表的第一个节点开始，每次数m个节点，然后把这个节点从链表中删除。然后，我们再从被删除节点的下一个节点开始继续数m个节点，直到所有节点都被删除为止。

下面是用C++代码实现头插法建立循环链表解决约瑟夫问题的示例：

#include <iostream>
using namespace std;

// 定义节点
struct Node {
    int data; // 保存节点数据
    Node* next; // 指向下一个节点的指针
};

// 头插法建立循环链表
Node* createCircularLinkedList(int n) {
    Node* head = nullptr; // 链表头节点
    for (int i = n; i > 0; i--) { // 从最后一个节点开始插入
        Node* node = new Node(); // 创建新节点
        node->data = i; // 设置新节点的数据
        node->next = head; // 把新节点插入到头部
        head = node; // 更新头节点
    }
    // 链表头尾相连，形成循环链表
    Node* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
    }
    tail->next = head;
    return head;
}

// 解决约瑟夫问题
void josephus(int n, int m) {
    Node* head = createCircularLinkedList(n); // 创建循环链表
    Node* p = head; // 指向当前节点
    while (n-- > 0) {
        for (int i = 1; i < m; i++) { // 数m个节点
            p = p->next;
        }
        cout << p->data << " "; // 输出出圈节点的数据
        Node* q = p->next; // 保存下一个节点的指针
        *p = *q; // 把下一个节点的数据复制到当前节点
        delete q; // 删除下一个节点
    }
    cout << endl;
}

int main() {
    int n = 8;
    int m = 3;
    josephus(n, m);
    return 0;
}