链表求解约瑟夫环问题

约瑟夫环问题是一个经典的数学问题，其具体描述是：n个人围成一圈，从第一个人开始报数，报到m的人出圈，下一个人再从1开始报数，报到m的人出圈，以此类推，直到所有人出圈，求出所有人出圈的顺序。

解决该问题的一种常见方式是使用循环链表。具体步骤如下：

1. 创建一个循环链表，将n个人依次加入链表中。

2. 从第一个人开始报数，每报到第m个人就将其从链表中删除。

3. 将被删除的人的编号记录下来，并将其从链表中删除。

4. 重复步骤2和步骤3，直到链表为空，所有人都出圈。

下面是使用C++语言实现的代码：

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
};

int josephus(int n, int m) {
    Node *head = new Node(1);
    Node *cur = head;
    for (int i = 2; i <= n; i++) {
        cur->next = new Node(i);
        cur = cur->next;
    }
    cur->next = head;

    Node *prev = cur;
    cur = head;
    int cnt = 0;
    while (cur->next != cur) {
        cnt++;
        if (cnt == m) {
            prev->next = cur->next;
            cnt = 0;
            cout << cur->val << " ";
            delete cur;
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }

    int ans = cur->val;
    delete cur;
    return ans;
}

int main() {
    int n = 7, m = 3;
    cout << josephus(n, m) << endl;  // 输出：4
    return 0;
}

在上述代码中，我们使用了一个结构体`Node`来表示链表中的节点。在函数`josephus`中，我们首先创建一个循环链表，然后从头节点开始进行报数。每当报到第m个人时，就将该人从链表中删除，并记录其编号。最后，当链表中只剩下一个节点时，该节点即为最后一个出圈的人，我们将其编号返回即可。

该算法的时间复杂度为O(nm)，空间复杂度为O(n)。