企业官网建设流程全解析

题目链接：141. 环形链表 - 力扣（LeetCode） 难度：简单 | 标签：哈希表、链表、双指针

一、先看清题目在问什么

给你一个链表的头节点head，判断链表里有没有环。

如果有某个节点，可以通过连续next指针再次走到它自己，就说明有环。

注意题目给的数组形式只是"造链表"的描述：pos表示尾节点接回到第几个下标（pos = -1表示无环），这个pos是不会传给函数的，函数只能拿到head。

一条链表长什么样

无环： 1 -> 2 -> 3 -> 4 -> nullptr ^ 走到头，结束 ​ 有环： 1 -> 2 -> 3 -> 4 ^ | | v +-------- 5 (4 的 next 指回 2)

一旦有环，顺着next一直走就永远走不到 nullptr，会无限循环。这就是我们要检测的东西。

函数签名

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { } };

二、一个必须先纠正的关键点

你的原始思路写的是：

遍历找到之前出现的数据就说明有环

这里藏着本题最大的一个坑：要判断"出现过"的是节点本身（指针/地址），不是节点里的值val。

if (p->val == q->val) // ❌ 错误！值相同不代表是同一个节点 if (p == q) // ✅ 正确！地址相同才是同一个节点

举个反例：

链表： 3 -> 7 -> 3 -> nullptr (pos = -1，无环)

两个节点的val都是 3，但它们是两个不同的节点。如果比值，你会误判成"有环"。

一句话记住：链表有没有环，看的是"拓扑结构"，跟存的值毫无关系。

下面三种解法，本质上都是在回答同一个问题：我在往前走的过程中，有没有踩到一个我以前来过的节点？区别只是"怎么记录以前来过哪里"。

三、解法一：朴素双循环（最容易想到的）

思路

对每一个当前节点cur，回头从头扫一遍它前面所有的节点，看看是不是"同一个节点"出现过。 如果有 → 说明有人指回了老地方 → 有环。

cur 停在 ⑤： ① -> ② -> ③ -> ④ -> ⑤ -> ③（环） ^ cur 回头扫：pre 从 ① 走到 cur 前面，逐个比 (pre == cur)

代码

class Solution { public: bool hasCycle(ListNode *head) { for (ListNode *cur = head; cur != nullptr; cur = cur->next) { // 回头检查：cur 这个"节点"，是不是之前就出现过 for (ListNode *pre = head; pre != cur; pre = pre->next) { if (pre == cur) return true; // 撞见了老朋友 -> 有环 } } return false; // 能一路走到 nullptr -> 无环 } };

⚠️ 一个很容易写错的版本（实测踩过的坑：Case 3head=[1]输出 true）

把内层循环的条件从pre != cur写成pre != nullptr，看起来"更自然"，结果直接错误：

// ❌ 错误写法 —— 任何非空链表都会返回 true for (ListNode *cur = head; cur != nullptr; cur = cur->next) { for (ListNode *pre = head; pre != nullptr; pre = pre->next) { if (pre == cur) return true; // ← cur 一进来就会"撞见自己" } }

错在哪：内层pre从head一路走到nullptr，途中必然经过cur自己。 所以只要链表非空，第一轮外层循环时pre走到cur的位置就pre == cur成立，立刻return true—— 连无环的head = [1]（LeetCode Case 3）都会被判成有环，输出true、期望false。

根因：我们要找的是"cur在之前的节点里出现过"，也就是在[head, cur)这个左闭右开区间里找。cur自己不在"以前来过"的集合里，所以内层扫描必须在到达cur之前停下。

// ✅ 正确写法：内层循环边界是 pre != cur，把 cur 自己排除在外 for (ListNode *pre = head; pre != cur; pre = pre->next) { if (pre == cur) return true; // 只可能由"别人指回来"触发 }

一句话记住：回头检查时，永远不要把"现在的自己"算进"过去"。内层循环走到cur就必须停（pre != cur），否则cur一定会和自己撞上。

顺带一提：改成正确写法后，if (pre == cur)这行其实永远可以简化成return true;（循环能正常结束走到cur，说明没撞上；能触发判断说明撞上了），但保留比较写出来更清晰、不易写错。

复杂度

为什么它能停下来？

有环时外层for确实会死循环，但内层循环会在有限步内找到那个重复节点并return true，所以整体一定会结束。

评价

✅ 最符合直觉，不需要任何额外数据结构 ❌ 太慢，n = 10⁴ 时就要比 10⁸ 次量级，会超时

四、解法二：哈希集合（第一次优化 —— 用空间换时间）

思路

解法一慢，是因为每次都要"重新走一遍"去回忆。 那干脆拿个小本本（哈希集合）记下来：每走到一个新节点，就把它的地址存进去；下次再看这个地址在不在本本里。

走到 ③ -> 不在本本里 -> 记下来 {①②③} ... 又走到 ③ -> 本本里有！-> 有环 ✅

unordered_set的查找是平均 O(1)，所以从"每次 O(n) 地回忆"降到了"每次 O(1) 地查表"。

代码

#include <unordered_set> ​ class Solution { public: bool hasCycle(ListNode *head) { std::unordered_set<ListNode*> seen; // 小本本：存"节点地址" ​ for (ListNode *cur = head; cur != nullptr; cur = cur->next) { if (seen.count(cur)) return true; // 这个节点以前来过 -> 有环 seen.insert(cur); // 没来过，记下来 } return false; } };

复杂度

评价

✅ 时间复杂度从 O(n²) 降到了 O(n)，非常好理解 ❌ 额外占了 O(n) 的内存 —— 面试官一般会追问"能不能不用额外空间？"

这是从你的思路 1 最自然的升级：把"用循环反复找"换成"用集合一次性记住"。

五、解法三：快慢指针 Floyd（最优解 —— 推荐背下来）

思路

不用本本，用两个人跑步：

• 🐢慢指针 slow：一次走1 步

• 🐇快指针 fast：一次走2 步

① -> ② -> ③ -> ④ -> ⑤ ^ | +--------------+

• 如果没环：跑道是直的，跑得快的fast一定会先撞到终点nullptr。→ 返回false

• 如果有环：跑道是环形的，两个人一直在里面转。fast比slow快，它必然会从后面追上 slow并和它重合。→ 返回true

打个比方：在操场跑道上跑步，跑得快的人一定会套圈追上跑得慢的人。

为什么一定会追上（不用怕想不明白）

把两人的相对速度看成2 - 1 = 1 步/次。 两个人进入环以后，快指针相对慢指针每"回合"缩短 1 个节点的距离。

而环的长度是有限的（设为 b），距离最多就是 b-1，所以最多再走 b-1 回合，距离一定会缩到 0，也就是相遇。

并且永远不用担心"擦肩而过跳过"—— 相对速度恰好是 1，是一格一格逼近的，只能严格减 1，不可能从 1 直接跳到 -1。

代码（LeetCode 可直接提交，无需 include）

class Solution { public: bool hasCycle(ListNode *head) { ListNode* slow = head; ListNode* fast = head; ​ // 注意顺序：必须先判 fast，再判 fast->next，否则可能空指针解引用 while (fast != nullptr && fast->next != nullptr) { slow = slow->next; // 走 1 步 fast = fast->next->next; // 走 2 步 ​ if (slow == fast) return true; // 追上了 -> 有环 } return false; // fast 走到 nullptr 了 -> 无环 } };

💡 先走再判、还是先判再走？ 两个指针初始都指向head，此时slow == fast但还没开始跑，不能算相遇。所以必须先走一步再判断上面这种写法是安全的。

手写模拟一遍（有环，环入口是 ②）

初始： slow=① fast=① 第1轮后： slow=② fast=③ 不等 第2轮后： slow=③ fast=⑤ 不等 第3轮后： slow=④ fast=② 不等 (fast 已经进环又绕回来了) 第4轮后： slow=⑤ fast=④ 不等 第5轮后： slow=② fast=② 相等 ✅ 返回 true

复杂度

评价

✅ 时间最优、空间最优，代码只有 8 行 ✅ Top 100 高频题的标准答案，面试必须会

六、三种解法横向对比

进化路径也很好记：

想法：找重复节点 │ ├─ 用时间换空间 ──> 双循环：每个节点都回头扫（慢，O(n²)） │ └─ 换个方式记录 ──> 哈希集合：用小本本记下来（快，但占内存 O(n)） │ └─ 还能更好吗？──> 快慢指针：靠"套圈"物理性质判断（O(1) 空间）

七、易错点清单

边界用例自查

八、延伸：找到环的入口节点（LeetCode 142）

141 的姊妹题。只需要在快慢指针相遇后再多加几行：

结论：快慢指针相遇时，把其中一个指针放回head，然后两个指针都改成一次走 1 步，它们再次相遇的位置，就是环的入口。

class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { // 第一次相遇：确认有环 slow = head; // 一个回到起点 while (slow != fast) { // 两个都走 1 步 slow = slow->next; fast = fast->next; } return slow; // 再次相遇处 = 环入口 } } return nullptr; } };

为什么成立（记住这几个量）：

head ──a──> 环入口 ──b──> 相遇点 ──c──> （绕回环入口） ​ 第一次相遇时，slow 走了 a + b，fast 走了 2(a + b) fast 比 slow 多走的，恰好是「若干圈环长」： 2(a + b) - (a + b) = k(b + c) => a + b = k(b + c) => a = (k-1)(b + c) + c

右边c是"从相遇点再走到入口"的距离，(k-1)(b+c)是整圈（绕几圈不影响终点）。 所以a（head 到入口的距离） == 从相遇点再走c+ 若干圈，两者同时以 1 步/次前进，必然在环入口碰头。

九、一句话总结

判断链表有没有环，最快的方法是让两个指针一快一慢同时跑：fast跑到nullptr就是没环，追上slow就是有环 —— 时间 O(n)，空间 O(1)。

建议练习顺序：先手写解法一确认理解 → 再写解法二体会"空间换时间" → 最后默写解法三到能 30 秒写出来。