0142. Linked List Cycle II¶
题目信息¶
- 题号:
环形链表 II
- 难度:
Medium
- 主题:
链表、Floyd 快慢指针、环入口、距离同余
- 原题:
- 重点:
先以速度差确认并取得环内相遇点,再利用头部距离与环内偏移的同余关系定位入口
题目重述¶
给定可能含环的单链表 head。若存在环,返回从链表头沿 next 首次进入环的那个节点对象;无环返回
nullptr。测试说明中的 pos 只用于描述尾节点连回的位置,不是函数参数。不能修改链表,节点值也
不能代替节点身份。
自建示例¶
9 -> 4 -> 7 -> 2 -> 5,尾节点连回7:环入口是值为7的那个节点对象;1 -> 2 -> 3 -> nullptr:不存在环,返回空;单节点指向自身:头节点同时就是环入口;
若环从头节点开始,入口应返回
head,而不是快慢指针第一次相遇时的任意环内位置。
C++ 实现¶
#include <unordered_set>
class Solution {
private:
ListNode* firstRepeatedIdentity(ListNode* head) {
std::unordered_set<ListNode*> 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),因此:
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。
第二阶段步数 |
|
|
|---|---|---|
|
|
|
|
|
|
|
|
|
代码状态与主解选择¶
meeting == nullptr 只表示第一阶段没有相遇;一旦相遇,第二阶段不再需要空指针检查,因为两根指针沿
同一有限前缀或环内移动,已由证明保证会合。整个过程只比较地址、不写 next,链表结构保持不变。
公开入口采用 Floyd 两阶段算法。第一阶段至多走过非环前缀和常数圈,第二阶段走 mu 步,总时间
O(n)、空间 O(1)。集合方案同为线性时间且更贴近“首次重复”定义,但需要 O(n) 地址;保留它
作为从问题定义到常量状态推导的基线。