利用后插法创建单向循环链表模拟猴子选大王问题实现依次输出出圈的猴子编号

猴子选大王的问题通常使用一种叫做“环形链表”的数据结构来模拟，因为在这种情况下，每次选择后，剩下的节点形成一个新的环形链表，直到只剩下最后一个被选中的猴子。后插法（insertion method）在这个场景中非常适合，因为它可以轻松地插入新的节点到链表尾部。

首先，我们需要定义一个链表节点结构体，包含节点值和指向下一个节点的指针：

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

然后，我们可以编写一个函数来创建一个空的环形链表：

Node* createCircularLinkedList() {
    return new Node{-1, nullptr}; // 初始化一个特殊的环形链表头结点，方便后续操作
}

接下来，我们创建一个函数来模拟猴子选大王的过程。这里假设有一个数组`arr`存储所有猴子的价值，我们用两个指针`prev`, `current`来遍历链表，同时保持`current`始终在`prev`之后：

void selectMonkey(int arr[], int n) {
    Node* head = createCircularLinkedList();
    Node* tail = head;
    
    for (int i = 0; i < n; ++i) {
        tail->next = new Node{arr[i], tail}; // 后插新节点到尾部
        tail = tail->next; // 更新tail为新插入的节点
    }
    
    tail->next = head; // 关闭环，使之成为单向循环

    current = head;
    prev = nullptr;
    while (true) {
        std::cout << current->value << " ";
        
        if (current == head) { // 如果当前节点是头结点，所有的猴子都已输出
            break;
        }

        // 更新指针，先移动prev，再移动current
        prev = current;
        current = current->next;

        // 当current等于prev时，说明它们相隔一轮，出圈了
        if (current == prev->next) {
            delete prev;
            prev = nullptr;
        }
    }
    delete head; // 删除头结点，释放内存
}

现在你可以调用`selectMonkey(arr, n)`，其中`arr`是你保存所有猴子价值的数组，`n`是猴子的数量。