GESP 五级 · GESP 202509 C++ 五级 第 3 题

函数 hasCycle 采用 Floyd 快慢指针法判断一个单链表中是否存在环，链表的头节点为 head，即用两个指针在链表上前进：slow 每次走 1 步，fast 每次走 2 步，若存在环，fast 终会追上 slow（相遇）；若无环，fast 会先到达 nullptr，则横线上应填写（ ）。

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

bool hasCycle(Node *head) {
    if (!head || !head->next)
        return false;
    Node* slow = head;
    Node* fast = head->next;
    while (fast && fast->next) {
        if (slow == fast) return true;
        ___________________ // 在此处填入代码
    }
    return false;
}

A.

slow = slow->next;
fast = fast->next->next;

B.

slow = fast->next;
fast = slow->next->next;

C.

slow = slow->next;
fast = slow->next->next;

D.

slow = fast->next;
fast = fast->next->next;

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

【考点】链表遍历｜Floyd 环检测｜指针操作

【解题思维】Floyd 算法的核心就是「快慢指针」：slow 每步走 1 个节点，fast 每步走 2 个节点。循环体里必须先更新 slow，再基于更新前的 fast 位置走两步。题中初始化让 fast 从 head->next 出发，所以循环里必须写 slow = slow->next; fast = fast->next->next;，这样才能保持 1:2 的相对速度差，遇环必相遇。

【陷阱拆解】C 选项 fast = slow->next->next 看似合理，实则把 fast 从当前 slow 位置再走两步，相当于 fast 每轮走 3 步，破坏算法原理；B、D 让 slow 跳到 fast 后面，更离谱。最阴险的是 C——很多人会下意识觉得「slow 先走，那 fast 就从 slow 走两步」，却忘了 fast 必须基于它自己的位置。如果只背结论，就会选 C 掉坑里。

【反命题思维】把题目改成「用哈希表判环」，横线填 seen.insert(slow)，复杂度从 O(1) 空间变成 O(n)；或者让 fast 每次走 3 步，问能否检测环，答案仍是能，只是相遇点会偏移。刷到类似 Floyd 题，先问自己：「快慢指针的速度比是多少？fast 该基于谁的位置移动？」