141. 环形链表（简单）

Blind 75 › 141. 环形链表（简单） （第 3 章）
文章工具

题目

给定一个单链表的头节点 head，判断这条链表中是否存在「环」。

存在环的意思是：链表中存在某个节点，从它沿 next 指针一直向后走，能再次回到它自己（也就是某条 next 链最终绕了回来）。存在返回 true，不存在返回 false。

评测内部会用整数 pos 表示“尾节点再指向第几个节点（从 0 开始计数）”；它只用于描述真实链路，不会作为参数传给你，你只能拿到 head。pos = -1 表示没有环。

自造示例：[1,2,3,4,5] 且 5.next → 2（pos=1）→ true；[1,2] 且 2.next → null → false；[1] 且 1.next → 1（自环）→ true。

约束：节点数 0 ~ 104；节点值 -105 ~ 105；pos 为 -1 或链表中的有效下标。进阶：能否用 O(1) 额外空间解决。

思路

一句话：让一个指针每次走 1 步、另一个走 2 步；有环它们一定相遇，无环快指针会先到末尾。

最直白的做法：边走边把经过的节点存进哈希集合；一旦发现 next 指向了已存过的节点，就说明绕回来了。时间 O(n)，但额外空间 O(n)，不满足进阶要求。

关键观察：把链表想象成“一条直路 + 一圈跑道”。

  • 无环：快指针会先撞到 null，说明是一条线，返回 false。
  • 有环：两个指针先后进入环内后，快指针相对慢指针每轮只多前进 1 个节点；差距每轮减 1，不会“跳过头而永久错过”，总有一轮差距变为 0，即两指针重合。

因此选「快慢指针 / 龟兔赛跑」，时间 O(n)、空间 O(1)。

解法

设置 slow 一次走一步、fast 一次走两步。循环条件只要 fast 与 fast.next 都非空，就移动后比较；相等返回 true。以下用 1→2→3→4→5、5.next → 2 跟踪：

状态slow 指向fast 指向比较结果
开始11不比较
第 1 轮23不等
第 2 轮35不等
第 3 轮43不等
第 4 轮55相等 → 有环

移动一次再比较，避免两指针都从 head 出发时“一开始就相等”的假阳性。

下图把上面的关键过程画成示意图，并逐步演示：

141. 环形链表（简单） 关键过程示意图
图① 关键过程示意图。
141. 环形链表（简单） 逐步演示动画
动图② 逐步演示（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 bool hasCycle(ListNode *head) {
 ListNode *slow = head;
 ListNode *fast = head;
 while (fast != nullp
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。