猴子选大王c++链表

在C++中，猴子选大王是一个经典的问题，可以通过链表来解决。具体的实现步骤如下：

1. 首先，我们需要定义一个链表节点的结构体，包含一个数据成员和一个指向下一个节点的指针。

struct ListNode {
    int data;
    ListNode* next;
};

2. 接下来，我们需要创建一个循环链表，并初始化每个节点的数据。

ListNode* createCircularLinkedList(int n) {
    ListNode* head = new ListNode;
    head->data = 1;
    head->next = nullptr;
    ListNode* prev = head;

    for (int i = 2; i <= n; i++) {
        ListNode* newNode = new ListNode;
        newNode->data = i;
        newNode->next = nullptr;
        prev->next = newNode;
        prev = newNode;
    }

    prev->next = head; // 将最后一个节点的next指针指向头节点，形成循环链表

    return head;
}

3. 然后，我们需要实现猴子选大王的算法。算法的思路是，从头节点开始，每次数到第m个节点，将该节点从链表中删除，直到只剩下一个节点为止。

int monkeyKing(ListNode* head, int m) {
    ListNode* curr = head;
    ListNode* prev = nullptr;

    while (curr->next != curr) {
        // 数到第m个节点
        for (int i = 1; i < m; i++) {
            prev = curr;
            curr = curr->next;
        }

        // 删除当前节点
        prev->next = curr->next;
        delete curr;
        curr = prev->next;
    }

    return curr->data; // 返回最后剩下的节点的数据
}

4. 最后，我们可以调用上述函数来解决猴子选大王问题。

int main() {
    int n = 10; // 猴子的数量
    int m = 3; // 数到第m个猴子

    ListNode* head = createCircularLinkedList(n);
    int king = monkeyKing(head, m);

    cout << "The monkey king is: " << king << endl;

    return 0;
}

这样，我们就可以通过链表来实现猴子选大王的问题了。