第4题下列C++代码用循环链表解决约瑟夫问题，即假设n个人围成一圈，从第一个人开始数，每次数到第k个的人就出圈，输出最后留下的那个人的编号。横线上应填写（）。

第 180 题 / 共 251 题

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

Node* createCircularList(int n) {
    Node* head = new Node{1, nullptr};
    Node* prev = head;

    for (int i = 2; i <= n; ++i) {
        Node* node = new Node{i, nullptr};
        prev->next = node;
        prev = node;
    }

    prev->next = head;
    return head;
}

int findLastSurvival(int n, int k) {
    Node* head = createCircularList(n);
    Node* p = head;
    Node* prev = nullptr;

    while (p->next != p) {
        for (int count = 1; count < k; ++count) {
            prev = p;
            p = p->next;
        }
       ___________________________
    }

    cout << "最后留下的人编号是: " << p->data << endl;
    delete p;

    return 0;
}

🎉

回答正确！

你真棒！

📝 题目解析

答案：A

知识点：循环链表的应用，约瑟夫问题的解决思路

解析：约瑟夫问题中，出圈操作需先将前一个节点的next指向当前节点的下一个节点（跳过当前节点），再删除当前节点，最后更新当前指针。B和C先删除p会导致无法访问p->next，D删除了新的p导致错误，因此A正确。