快慢指针
解题思路
初始化快慢指针，随后 slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置；
如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇；
复杂度
-
时间复杂度：
O(N)，其中 N 为链表中节点的数目； -
空间复杂度：
O(1)；
代码实现
var hasCycle = function (head) {
if (head === null || head.next === null) return false;
// 快慢指针
let slow = head;
let fast = head.next;
while (slow !== fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
};
哈希
解题思路
遍历链表并用 Hash 进行存储；
如果产生重复遍历则代表有环；
复杂度
-
时间复杂度：
O(n)，其中 n 是链表节点数； -
空间复杂度：
O(n)，其中 n 是链表节点数；
代码实现
var hasCycle = function (head) {
if (head === null) return false;
let set = new Set();
while (head) {
if (set.has(head)) return true;
set.add(head);
head = head.next;
}
return false;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
509.斐波那契数
上一篇
评论
