0141. Linked List Cycle¶
题目信息¶
- 题号:
环形链表
- 难度:
Easy
- 主题:
链表、Floyd 快慢指针、对象身份、环检测
- 原题:
- 重点:
从“节点身份重复”定义环,再用两个不同速度的指针把访问集合压缩为常量状态
题目重述¶
给定单链表头节点 head,判断沿 next 不断前进时是否会再次到达同一个节点对象。节点值相同不代表
有环,必须比较节点身份。测试说明中的 pos 只是描述尾节点连回哪个位置,并不是函数参数。进阶要求只
使用 O(1) 额外空间。
自建示例¶
8 -> 3 -> 5 -> 1,尾节点的next指回节点3:沿链会重复访问同一个3,返回true;三个不同节点的值都为
4,但最后指向nullptr:返回false;单节点的
next指向自身:返回true;空链和单节点无环链都返回false。
C++ 实现¶
#include <unordered_set>
class Solution {
private:
bool rememberVisitedNodes(ListNode* head) {
std::unordered_set<ListNode*> visited;
for (ListNode* node = head;
node != nullptr;
node = node->next) {
if (!visited.insert(node).second) {
return true;
}
}
return false;
}
bool meetWithDifferentSpeeds(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
public:
bool hasCycle(ListNode* head) {
return meetWithDifferentSpeeds(head);
}
};
题解¶
先把“有环”翻译为可检测事件¶
从头沿唯一的 next 路径前进,只有两种结局:到达 nullptr,说明路径有限且无环;或者再次到达某个
已经见过的节点对象,此后路径会永久重复,说明存在环。最直接的 rememberVisitedNodes 把每个节点地址
放入集合;插入失败就表示同一地址第二次出现。
集合必须存 ListNode*,不能存 val。两个不同节点即使值相同仍可依次出现在一条普通链上;环的定义
是引用结构回到同一对象,而不是数据重复。该方案一次扫描即可判定,时间 O(n),但最坏保存 O(n)
个地址。
不用保存历史,能否制造一个必然相遇的状态¶
若链表有环,进入环后的运动只剩有限个模环长位置。让 slow 每轮走一步,fast 每轮走两步;两者都
进入环后,快指针相对慢指针每轮前进一步。若环长为 lambda,相对距离按模 lambda 依次增加一,
最多 lambda 轮必有一次变为零,即两个指针指向同一节点。
这里不需要知道环从哪里开始或环有多长。两个指针的位置把“是否访问过”问题转化为“速度差是否在有限环上 追平”,从而删除访问集合。
有环时为何两者都会进入环¶
从头到环入口的链只有有限长度。慢指针最终进入环;快指针沿同一条 next 路径移动且不会遇到空指针,
所以也会进入。一旦进入,next 永远留在环内。快指针可能在慢指针入环前已经绕行若干次,但这只改变
初始相对位置,不影响每轮相对前进一步的结论。
无环时为何不会误报¶
有限无环链最终指向 nullptr。快指针每轮走两步,因此迟早出现 fast == nullptr 或
fast->next == nullptr,循环结束并返回假。循环守卫必须同时检查这两个条件,才能安全执行
fast->next->next。
指针从同一点出发为何不立即判真¶
初始化时 slow == fast == head 只是人为把两个观察者放在起点,不是“沿链再次访问”。代码先各自移动,
再比较;否则任何非空链在零步时都会被误判为有环。
输入结构 |
第一次移动后 |
结果路径 |
|---|---|---|
空链 |
守卫失败,不移动 |
返回 |
单节点无环 |
|
返回 |
单节点自环 |
|
移动后相等,返回 |
多节点有环 |
两者以速度差一在环中追逐 |
最迟一圈内相遇 |
代码对应与主解选择¶
slow、fast 始终是从头沿真实 next 路径可达的节点,不会产生伪造相遇;指针相等表示对象身份
相同,而非值相等。相遇即可证明存在闭合路径,无需再定位入口。
公开入口采用 Floyd 快慢指针,时间 O(n)、额外空间 O(1)。地址集合方案同为线性时间,定义对应
最直接,适合先建立正确性;快慢指针则利用单链表每个节点只有一个后继的结构,将全部访问历史压缩为两个
位置。两种方案都不修改链表。