快慢指针
解题思路
初始化两个指针 fast 与 slow ，起始都位于链表的头部；随后 slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置；如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇；
推导：
- 设链表中环外部分的长度为 a ，slow 指针进入环后，又走了 b 的距离与 fast 相遇，此时 fast 指针已经走完了环的 n 圈，因此：fast 走过的总距离为
a + n(b + c) + b=>a + (n + 1)b + nc；slow 走过的总距离为a + b；- 任意时刻 fast 指针走过的距离都为 slow 指针的 2 倍，则有
a + (n + 1)b + nc = 2(a + b)⟹a = c + (n − 1)(b + c)；- 有了
a = c + (n - 1)(b + c)的等量关系会发现：从相遇点到入环点的距离 c 加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离，即c === a；- 因此，当发现 slow 与 fast 相遇时，再额外使用一个指针 ptr 起始指向链表头部，随后 ptr 和 slow 每次向后移动一个位置，最终它们会在入环点相遇；
复杂度
-
时间复杂度：
O(N)，其中 N 为链表中节点的数目； -
空间复杂度：
O(1)
代码实现
var detectCycle = function (head) {
// 1. 初始化快慢指针
let slow = head, fast = head;
// 2. 找到相遇点
while (true) {
// 没有环，直接返回 null
if (fast == null || fast.next == null) return null;
slow = slow.next;
fast = fast.next.next;
// 找到相遇点，跳出循环
if (fast == slow) break;
}
// 3. 利用 a===c 找到环切点
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
};
哈希
解题思路
遍历链表中的每个节点，并将它记录下来；
一旦遇到了此前遍历过的节点，就可以判定链表中存在环；
复杂度
-
时间复杂度：
O(N)，其中 N 为链表中节点的数目； -
空间复杂度：
O(N)，其中 N 为链表中节点的数目；
代码实现
var detectCycle = function (head) {
if (head === null) return head;
let set = new Set();
while (head) {
if (set.has(head)) return head;
set.add(head);
head = head.next;
}
return null;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 141. 环形链表
上一篇
评论
