循环单链表求约瑟夫问题

循环单链表是一个环形链表，最后一个节点的 next 指针指向头结点。求解约瑟夫问题可以利用循环单链表模拟，具体步骤如下：

1. 构建循环单链表，将每个人的编号作为节点的数据域，将每个节点的 next 指针指向下一个节点。

2. 定义一个计数器 count，用于记录当前数到了第几个节点。

3. 从头节点开始遍历链表，每次计数器加1，直到计数器的值等于 m 时，就找到了要删除的节点。将该节点从链表中删除，并将计数器 count 重置为 0。

4. 重复步骤 3，直到链表中只剩下一个节点，此时该节点即为最后一个幸存者的编号。

下面是具体的代码实现：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int josephus(int n, int m) {
    ListNode* head = new ListNode(1);
    ListNode* cur = head;
    for (int i = 2; i <= n; i++) {
        cur->next = new ListNode(i);
        cur = cur->next;
    }
    cur->next = head; // 构造循环链表

    int count = 0;
    while (cur->next != cur) { // 链表中还有多于一个节点
        count++;
        if (count == m) {
            ListNode* temp = cur->next;
            cur->next = temp->next;
            delete temp; // 释放要删除的节点
            count = 0;
        } else {
            cur = cur->next;
        }
    }

    int ans = cur->val;
    delete cur; // 释放最后一个节点
    return ans;
}

int main() {
    int n = 5, m = 2;
    int ans = josephus(n, m);
    cout << "The last survivor's number is: " << ans << endl;
    return 0;
}