企业官网建设流程全解析

前言

LeetCode 142 的题目是：给定一个单链表的头结点，如果链表中有环，返回环的入口结点；如果无环，返回空。要求不使用额外空间（进阶要求 O(1) 空间）。这是 141 题「判断是否有环」的后续：141 只问有没有，142 要定位入口。

常见的误解有三个。第一，以为快慢指针相遇的那个结点就是入口——相遇点在环内，但不一定是入口，除非头结点到入口的距离恰好是环长的整数倍。第二，以为需要先求出环长再从头走——求环长是一种可行思路，但不是必须的，Floyd 算法在相遇后直接重置一个指针就能找到入口。第三，循环条件只写fast != nullptr，然后在循环体里访问fast->next->next，遇到空指针直接崩溃。

本文先讲快慢指针的相遇条件，再用代数推导说明「相遇后重置一个指针，两个指针每次走一步，再次相遇处就是入口」，然后给出完整代码和求环长的变体，最后列出边界与常见错误。

一、快慢指针为什么一定会相遇

设两个指针从同一个头结点出发，慢指针每次走一步，快指针每次走两步。如果链表无环，快指针会先到达末尾，循环结束，不会相遇。如果有环，两个指针都进入环后，快指针相对慢指针每次多走一步，相当于在环内以相对速度 1 追赶，而环是有限的，所以一定会在某个结点追上。

这里有一个容易忽略的初始化问题：两个指针初始都指向头结点，如果循环一开始就比较slow == fast，会立刻判定「相遇」，即使链表无环。正确的做法是先移动、再比较，或者用do-while并确保至少移动一次。下面的代码采用「先移动后比较」。

快指针的循环条件必须同时检查fast和fast->next：

• 
  
• fast == nullptr：已经走到末尾，无环；
• 
  
• fast->next == nullptr：快指针只能再走一步，无法完成两步，无环。
• 
  

只检查fast是不够的，因为循环体里要取fast->next->next，当fast->next为空时会解引用空指针。这是单链表快慢指针最常见的崩溃点。

二、相遇点到入口的推导

设：

• 
  
• 头结点到环入口的距离为 a（经过 a 条边到达入口）；
• 
  
• 入口到相遇点的距离为 b（沿环的前进方向）；
• 
  
• 环的长度为 L。
• 
  

慢指针走过的距离是 a + b。快指针速度是慢指针的两倍，走过的距离是 2(a + b)。另一方面，快指针在环里可能多转了几圈，所以它的距离也可以写成 a + b + kL，其中 k 是正整数（至少多走一圈才会追上）。

两边相等：

2(a + b) = a + b + kL
a + b = kL
a = kL - b

把kL - b改写成(k - 1)L + (L - b)。这个式子的含义是：从头结点走 a 步到达入口；从相遇点出发，走L - b步绕到入口，再走(k - 1)整圈，同样到达入口。

于是算法是：相遇后，把一个指针放回头结点，另一个留在相遇点，两个指针每次都走一步。走 a 步后，从头出发的指针到达入口；从相遇点出发的指针也正好到达入口（可能多绕了 k-1 圈）。两者相遇的位置就是入口。

这个推导不依赖 a、b、L 的具体数值，也不要求 k 等于 1。无论快指针在环里转了几圈，结论都成立。

三、完整实现

// 适用于 C++17
struct ListNode {
int val = 0;
ListNode* next = nullptr;
};

ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;

while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // 慢指针一步
fast = fast->next->next; // 快指针两步

if (slow == fast) {
// 相遇：一个指针回到头，两个都每次一步
ListNode* p = head;
while (p != slow) {
p = p->next;
slow = slow->next;
}
return p; // 入口
}
}
return nullptr; // 无环
}

执行过程分两段：

第一段是判环。slow、fast同步出发，fast每次两步。如果fast或fast->next为空，说明走到了链尾，返回空。否则继续，直到slow == fast。

第二段是找入口。把p指回头结点，slow留在相遇点，两个指针每次各走一步。当p == slow时，该结点就是入口。注意此时slow已经不是在追fast，而是作为「从相遇点出发」的指针使用；变量名没变，角色变了。

返回类型是ListNode*，不是下标或值。题目要求返回结点本身，调用方可能通过它访问后续结点。

四、求环长的变体

如果题目还要求环的长度，可以在相遇后让一个指针留在原地，另一个沿环走一圈，回到起点时经过的步数就是 L：

// 适用于 C++17
int cycleLength(ListNode* meeting) {
if (meeting == nullptr) {
return 0;
}
int len = 1;
for (ListNode* p = meeting->next; p != meeting; p = p->next) {
++len;
}
return len;
}

有了环长 L，也可以这样找入口：两个指针从头出发，一个先走 L 步，然后两个同步前进，相遇处就是入口。这与「长度差」的思路一致——先走 L 步的指针相当于提前绕完一圈，两个指针到入口的距离相等。两种方法都对，Floyd 的重置法不需要额外计算环长，代码更短。

五、另一种解法：哈希集合

最直观的做法是遍历链表，把每个结点的指针放进std::unordered_set，第一个重复出现的结点就是入口：

// 适用于 C++17
#include <unordered_set>

ListNode* detectCycleHash(ListNode* head) {
std::unordered_set<const ListNode*> seen;
for (ListNode* p = head; p != nullptr; p = p->next) {
if (!seen.insert(p).second) {
return p; // 之前见过，说明是入口
}
}
return nullptr;
}

insert返回std::pair<iterator, bool>，second为false表示元素已存在。时间 O(n)，空间 O(n)。它不满足 142 的进阶要求，但胜在容易理解和实现，面试时可以先说思路，再给 Floyd 版本。

注意集合里存的是const ListNode*，比较的是地址。如果存int值，值相同的不同结点会被误判为环，这在有重复值的链表里一定会出错。

六、复杂度与边界

时间复杂度说明：第一段慢指针最多走 O(n) 步；第二段从头到入口是 a 步，a < n，所以总体 O(n)。空间只用了几个指针，O(1)。

边界情况：

• 
  
• 空链表：head == nullptr，fast为空，循环不执行，返回空。
• 
  
• 单结点无环：fast->next == nullptr，循环不执行，返回空。
• 
  
• 单结点自环：next指向自己。第一轮slow = head->next = head，fast = head->next->next = head，相遇；重置p = head，p == slow立即成立，返回 head，正确。
• 
  
• 环的入口就是头结点：相遇后p = head，若p == slow直接返回；否则走若干步也会回到头。结果正确。
• 
  
• 链表很长但无环：快指针先到末尾，返回空，不会死循环。
• 
  

常见坑点

1. 初始就比较两个指针❌while (slow != fast) { ... }，两个指针都初始化到头结点，循环一次都不执行或直接误判。 ✅ 用while (fast && fast->next)，先移动再比较。

2. 快指针只检查自己❌while (fast != nullptr) { fast = fast->next->next; }——fast->next为空时解引用空指针。 ✅while (fast != nullptr && fast->next != nullptr)。

3. 把相遇点当入口❌ 相遇后直接return slow;。 ✅ 重置一个指针到头，两个每次一步，再次相遇才是入口。

4. 重置后仍然走两步❌p = p->next; slow = slow->next->next;—— 速度不一致，永远追不上。 ✅ 第二阶段两个指针都每次一步。

5. 比较结点的值❌if (p->val == q->val)判断相遇或入口。 ✅ 比较指针p == q，值相同的结点可能完全不同。

6. 修改链表来标记访问❌ 遍历时把next改掉或给val打标记，破坏输入结构。 ✅ 用快慢指针或哈希集合，不修改链表。

7. 第二阶段循环条件写错❌while (p != slow) { p = p->next; }只移动一个指针，slow不动，永远不相等。 ✅ 两个指针都前进，循环内各走一步。

8. 返回了错误的变量❌ 循环结束后return slow;，而slow可能已经越过入口。 ✅ 循环结束时p == slow，返回p或slow都可以，但要确保是在相等的那一刻返回。

总结

Floyd 算法的代码很短，但有两个必须记住的细节：快指针的循环条件要检查fast->next，相遇后的第二阶段两个指针都要放慢到一步。理解a = kL - b这个等式，就能明白为什么重置后一定在入口相遇，而不是在环内其他位置。