18063 圈中的游戏

### 思路

这个问题是经典的约瑟夫环问题。我们可以使用链表来模拟这个过程。具体步骤如下：
1. 创建一个循环链表，表示所有人。
2. 从第一个人开始，依次报数。
3. 每报到3的人退出圈子，直到只剩下一个人。

### 伪代码

```
function josephus(n):
    create a circular linked list with n nodes
    current = head of the list

    while more than one node in the list:
        move current to the next node twice (to skip two nodes)
        remove the node after current (the third node)

    return the value of the remaining node
```

### C++代码

#include <iostream>
using namespace std;

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

int findLastPerson(int n) {
    // 创建循环链表
    Node* head = new Node(1);
    Node* prev = head;
    for (int i = 2; i <= n; ++i) {
        prev->next = new Node(i);
        prev = prev->next;
    }
    prev->next = head; // 形成循环链表

    // 初始化指针
    Node* current = head;
    while (current->next != current) {
        // 移动两次
        for (int i = 0; i < 2; ++i) {
            current = current->next;
        }
        // 删除当前节点
        Node* temp = current->next;
        current->data = temp->data;
        current->next = temp->next;
        delete temp;
    }

    int lastPerson = current->data;
    delete current;
    return lastPerson;
}

int main() {
    int n;
    cin >> n;
    cout << findLastPerson(n) << endl;
    return 0;
}

### 总结

通过使用循环链表，我们可以有效地模拟报数和删除操作。每次报数到3时，删除相应的节点，直到只剩下一个节点。这个方法的时间复杂度是O(n)，适合处理较大的输入规模。