0141. Linked List Cycle
=======================
题目信息
--------
:题号: 0141. 环形链表
:难度: Easy
:主题: 链表、Floyd 快慢指针、对象身份、环检测
:原题: `LeetCode 0141 `_
:重点: 从“节点身份重复”定义环,再用两个不同速度的指针把访问集合压缩为常量状态
题目重述
--------
给定单链表头节点 ``head``,判断沿 ``next`` 不断前进时是否会再次到达同一个节点对象。节点值相同不代表
有环,必须比较节点身份。测试说明中的 ``pos`` 只是描述尾节点连回哪个位置,并不是函数参数。进阶要求只
使用 ``O(1)`` 额外空间。
自建示例
--------
* ``8 -> 3 -> 5 -> 1``,尾节点的 ``next`` 指回节点 ``3``:沿链会重复访问同一个 ``3``,返回
``true``;
* 三个不同节点的值都为 ``4``,但最后指向 ``nullptr``:返回 ``false``;
* 单节点的 ``next`` 指向自身:返回 ``true``;空链和单节点无环链都返回 ``false``。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
bool rememberVisitedNodes(ListNode* head) {
std::unordered_set 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`` 只是人为把两个观察者放在起点,不是“沿链再次访问”。代码先各自移动,
再比较;否则任何非空链在零步时都会被误判为有环。
.. list-table::
:header-rows: 1
* - 输入结构
- 第一次移动后
- 结果路径
* - 空链
- 守卫失败,不移动
- 返回 ``false``
* - 单节点无环
- ``fast->next`` 为空,守卫失败
- 返回 ``false``
* - 单节点自环
- ``slow``、``fast`` 都仍指向该节点
- 移动后相等,返回 ``true``
* - 多节点有环
- 两者以速度差一在环中追逐
- 最迟一圈内相遇
代码对应与主解选择
~~~~~~~~~~~~~~~~~~
``slow``、``fast`` 始终是从头沿真实 ``next`` 路径可达的节点,不会产生伪造相遇;指针相等表示对象身份
相同,而非值相等。相遇即可证明存在闭合路径,无需再定位入口。
公开入口采用 Floyd 快慢指针,时间 ``O(n)``、额外空间 ``O(1)``。地址集合方案同为线性时间,定义对应
最直接,适合先建立正确性;快慢指针则利用单链表每个节点只有一个后继的结构,将全部访问历史压缩为两个
位置。两种方案都不修改链表。