c++有头指针的单循环链表解决约瑟夫问题

在 C++ 中，头指针的单循环链表可以用于解决约瑟夫环问题（Josephus Problem），这是一个经典的数学问题，涉及到一个等间距删除节点的序列。在链表中，每个节点有一个整数值和一个指向下一个节点的指针。当设置一个步长（通常从 2 开始，比如每隔一个节点删除）时，我们可以遍历链表并按照规则删除节点。

下面是解决该问题的基本步骤：

1. 初始化链表和步长（k）。
2. 创建一个计数器变量，初始值设为 1，表示第一个轮到的人。
3. 定义一个辅助函数，它会从链表的当前节点开始，每次移动 k 步，并删除节点。如果到达链表的末尾再回到头，就继续删除直到计数器等于步长。
4. 当计数器达到步长时，更新计数器并移动到新的节点位置。
5. 重复步骤 3 和 4 直到链表只剩下一个节点，这就是剩余的“存活者”。

下面是一个简单的伪代码示例：

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

Node* josephus(Node* head, int step) {
    if (head == nullptr || step <= 0) return nullptr;

    Node* current = head;
    Node* last = nullptr;
    int counter = 1;

    while (current != nullptr) {
        last = current;
        current = current->next;
        
        // 如果到了链表末尾，重新从头开始
        if (current == head) {
            counter++;
            continue;
        }

        // 删除节点
        if (counter % step == 0) {
            delete last;
        } else {
            counter %= step; // 保持计数器小于步长
        }
    }

    return head;
}