c++链表实现约瑟夫问题

好的，让我们开始讨论 c 链表实现约瑟夫问题。

约瑟夫问题是一个经典的数学问题，它描述了一个有 n 个人围成一圈报数，每报到第 m 个人就退出圈子，直到剩下最后一个人。它可以用链表来实现。

具体来说，我们可以先构建一个有 n 个节点的链表，并把它们依次连接起来形成一个环。接下来从第一个节点开始遍历，每到第 m 个节点就删除它并重新连接链表，直到只剩下一个节点为止。

代码实现如下（假设节点编号从1开始）：

struct Node {
int val;
Node* next;
Node(int v): val(v), next(nullptr) {}
};

Node* josephus(int n, int m) {
Node* prev = new Node(1);
Node* head = prev;
for (int i = 2; i <= n; i++) {
Node* cur = new Node(i);
prev->next = cur;
prev = cur;
}
prev->next = head; // 连成环
Node* cur = head;
while (n > 1) {
for (int i = 0; i < m-2; i++) {
cur = cur->next;
}
Node* temp = cur->next;
cur->next = cur->next->next; // 删除节点
delete temp;
n--;
}
return cur;
}

这样，当你调用josephus(n, m)时，它会返回最后剩下的节点。