0142. Linked List Cycle II ========================== 题目信息 -------- :题号: 0142. 环形链表 II :难度: Medium :主题: 链表、Floyd 快慢指针、环入口、距离同余 :原题: `LeetCode 0142 `_ :重点: 先以速度差确认并取得环内相遇点,再利用头部距离与环内偏移的同余关系定位入口 题目重述 -------- 给定可能含环的单链表 ``head``。若存在环,返回从链表头沿 ``next`` 首次进入环的那个节点对象;无环返回 ``nullptr``。测试说明中的 ``pos`` 只用于描述尾节点连回的位置,不是函数参数。不能修改链表,节点值也 不能代替节点身份。 自建示例 -------- * ``9 -> 4 -> 7 -> 2 -> 5``,尾节点连回 ``7``:环入口是值为 ``7`` 的那个节点对象; * ``1 -> 2 -> 3 -> nullptr``:不存在环,返回空; * 单节点指向自身:头节点同时就是环入口; * 若环从头节点开始,入口应返回 ``head``,而不是快慢指针第一次相遇时的任意环内位置。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: ListNode* firstRepeatedIdentity(ListNode* head) { std::unordered_set visited; for (ListNode* node = head; node != nullptr; node = node->next) { if (!visited.insert(node).second) { return node; } } return nullptr; } ListNode* locateEntryWithFloyd(ListNode* head) { ListNode* slow = head; ListNode* fast = head; ListNode* meeting = nullptr; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { meeting = slow; break; } } if (meeting == nullptr) { return nullptr; } ListNode* fromHead = head; while (fromHead != meeting) { fromHead = fromHead->next; meeting = meeting->next; } return fromHead; } public: ListNode* detectCycle(ListNode* head) { return locateEntryWithFloyd(head); } }; 题解 ---- 原始定义直接给出集合方案 ~~~~~~~~~~~~~~~~~~~~~~~~ 沿 ``next`` 前进时,第一次再次访问的节点就是环入口:入口之前的节点只出现一次,一旦进入环,最终最先 重复的正是入口。``firstRepeatedIdentity`` 用地址集合保存历史,插入失败时返回当前节点,时间 ``O(n)``、 空间 ``O(n)``。 集合中必须是节点指针。相同 ``val`` 的不同节点不构成重复,返回值也要求入口对象而不是入口的数值。要把 空间降为常量,需要先在不保存历史的情况下取得一个与环位置有关的锚点。 第一阶段:相遇只证明有环,还不一定是入口 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 慢指针每轮走一步,快指针走两步。无环时快指针必到达 ``nullptr``,代码通过 ``fast != nullptr && fast->next != nullptr`` 安全结束。有环时两者进入环后相对速度为一,最多一圈会在 某个环内节点相遇。 这个 ``meeting`` 通常不是入口。例如自建示例中,入口是 ``7``,快慢指针第一次相遇可以发生在后面的 ``2``。所以不能像上一题那样在相遇时直接返回,必须从运动距离中提取入口信息。 距离同余如何连接相遇点与入口 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 设: * ``mu`` 为头节点到环入口的边数; * ``lambda`` 为环长; * ``x`` 为相遇点从入口沿环前进的偏移,``0 <= x < lambda``; * ``t`` 为慢指针到第一次相遇时走过的总步数。 快指针走了 ``2t`` 步。两者在同一环位置,路程差 ``t`` 必是整圈长度的倍数,所以 ``t ≡ 0 (mod lambda)``。慢指针的路径又满足 ``t ≡ mu + x (mod lambda)``,因此: .. code-block:: text mu + x ≡ 0 (mod lambda) mu ≡ -x (mod lambda) 相遇点位于入口之后 ``x`` 步;从那里再走 ``mu`` 步,环内偏移变为 ``x + mu``,恰好是整圈倍数,最终 回到入口。 第二阶段为何把一根指针移回头 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 令 ``fromHead`` 从头出发,``meeting`` 留在第一次相遇点,两者都改为每轮一步。经过 ``mu`` 步: * ``fromHead`` 刚走完非环前缀,到达入口; * ``meeting`` 从偏移 ``x`` 又走 ``mu``,由上面的同余关系也到达入口。 在这之前 ``fromHead`` 仍位于环外、``meeting`` 已在环内,不可能指向同一对象,所以第二阶段第一次相等的 位置就是入口。若 ``mu = 0``,环从头开始;第一阶段相遇点也会在整圈后落回头,两指针无需移动便返回 ``head``。 具体走读 ``9 -> 4 -> 7 -> 2 -> 5 -> 7`` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 此时 ``mu = 2``、``lambda = 3``。第一阶段慢指针走三步到 ``2``,快指针走六步也到 ``2``,相遇点相对 入口偏移 ``x = 1``,满足 ``mu + x = 3``。 .. list-table:: :header-rows: 1 * - 第二阶段步数 - ``fromHead`` - ``meeting`` * - ``0`` - ``9`` - ``2`` * - ``1`` - ``4`` - ``5`` * - ``2`` - ``7`` - ``7``,返回入口 代码状态与主解选择 ~~~~~~~~~~~~~~~~~~ ``meeting == nullptr`` 只表示第一阶段没有相遇;一旦相遇,第二阶段不再需要空指针检查,因为两根指针沿 同一有限前缀或环内移动,已由证明保证会合。整个过程只比较地址、不写 ``next``,链表结构保持不变。 公开入口采用 Floyd 两阶段算法。第一阶段至多走过非环前缀和常数圈,第二阶段走 ``mu`` 步,总时间 ``O(n)``、空间 ``O(1)``。集合方案同为线性时间且更贴近“首次重复”定义,但需要 ``O(n)`` 地址;保留它 作为从问题定义到常量状态推导的基线。