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)``。地址集合方案同为线性时间,定义对应 最直接,适合先建立正确性;快慢指针则利用单链表每个节点只有一个后继的结构,将全部访问历史压缩为两个 位置。两种方案都不修改链表。