使用C语言中的循环链表解决

在C语言中，循环链表是一种特殊的链表结构，它的头节点指向尾节点，形成了一个闭合的环。对于使用循环链表解决问题，特别是像“猴子选大王”这样的问题，可以利用这种结构来简化遍历过程。由于每个节点都链接到下一个节点，我们可以设置一个指针来依次移动，同时处理循环性。

例如，在找到猴王的过程中，我们可以从任何一个节点开始，每次向前移动m个节点，直到所有的节点都被遍历过一次或者只剩下一个节点。这种方法的关键在于对模运算的使用，`(pos + m - 1) % n`可以保证指针始终在一个有效的范围内移动。

下面是一个简单的C语言代码片段，展示了如何使用循环链表解决这个问题：

typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建循环链表
Node* createCircularList(int n, int* arr) {
    Node* head = NULL;
    for (int i = 0; i < n; ++i) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = head;
        if (!head) {
            head = newNode;
        } else {
            head->next = newNode;
        }
    }
    return head;
}

// 寻找猴王
int findMonkeyKing(Node* head, int m) {
    Node* current = head;
    do {
        current = current->next;
    } while (--m > 0 && current != head); // 直到m变为1或者遇到头节点
    return current->data;
}

int main() {
    int n, m;
    int arr[] = {1, 2, 3, ..., n}; // 输入数组，假设你知道所有猴子编号
    Node* head = createCircularList(n, arr);
    int monkeyKing = findMonkeyKing(head, m);
    free(head); // 清理内存
    printf("猴王的编号为：%d\n", monkeyKing);
    return 0;
}