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

下面函数使用快慢指针查找单链表的中间结点。横线处应填写（　　）。

struct Node {
int value;
Node *next;
};
Node *middle(Node *head) {
Node *slow = head;
Node *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
______________________
}
return slow;
}

快指针每次走两步，慢指针每次走一步，当快指针到达末尾时，慢指针恰好在中间。这是链表找中点的经典技巧，时间复杂度O(n)，空间复杂度O(1)。看到题先想"快慢指针"，然后检查循环条件是否保证快指针不会越界。

选项A让快慢同速，永远追不上；选项C把快指针拉到慢指针后面，逻辑反了；选项D让快指针原地踏步。最阴险的是循环条件fast != nullptr && fast->next != nullptr，它保证了fast->next->next不会越界，但很多考生只盯着while条件，做题时却忘了检查快指针是否真的能走两步。

1. 考纲定位

GESP五级《数据结构与算法》模块，链表基础操作。命题人卡住的是"快慢指针"这个经典技巧——学生知道链表遍历，但一到双指针就懵，因为要同时维护两个指针的同步关系，比单指针复杂一个数量级。

2. 解题思维

看到"中间结点"四个字，第一反应就是快慢指针。慢指针走一步，快指针走两步，快指针到终点时慢指针正好在中间。

验证：链表长度n，快指针每次+2，慢指针每次+1。当快指针到达末尾（或末尾前一个）时，慢指针走了n/2步。循环条件fast != nullptr && fast->next != nullptr确保快指针至少还有两步可走，所以fast->next->next不会越界。

3. 陷阱拆解

• A选项：fast = fast->next，快慢同速，永远追不上，快指针到末尾时慢指针只走了一半路程。
• C选项：fast = slow->next，把快指针拉到慢指针后面，逻辑反了，快指针永远在慢指针后面。
• D选项：fast = head->next，快指针原地踏步，每次循环都回到第二个结点，死循环。
• 最阴险的细节：循环条件里同时检查fast和fast->next，这意味着fast->next->next是安全的。但很多考生只盯着while条件，做题时却忘了检查快指针是否真的能走两步，导致数组越界。

4. 反命题思维

如果把循环条件改成fast != nullptr，那么fast->next->next就会越界，必须改成fast->next != nullptr。如果改成fast->next != nullptr && fast->next->next != nullptr，那么奇数长度链表会停在中间偏右一个位置。

换个考法：让函数返回中间结点的值，或者返回中间两个结点的平均值（偶数长度），那就变成GESP六级难度了。