环形链表
🟢 简单题目描述
给你一个链表的头节点 head，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环，则返回 true。否则，返回 false。
示例 1
输入：head = [3, 2, 0, -4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点示例 2
输入：head = [1, 2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点示例 3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环提示
- 链表中节点的数目范围在
[0, 10^4]内 -10^5 <= Node.val <= 10^5pos为-1或者链表中的一个有效索引
解法一
参考答案 (2 个标签)
快慢指针 O(n)
思路
使用两个指针，慢指针每次走一步，快指针每次走两步。如果有环，快指针最终会追上慢指针。
代码实现
/**
* @param {ListNode} head
* @return {boolean}
*/
function hasCycle(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;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
为什么快慢指针一定能相遇？
想象两个人在环形跑道上跑步，快的人速度是慢的人的两倍。快的人一定会追上慢的人。
解法二
参考答案 (2 个标签)
哈希表 O(n)
思路
遍历链表，用哈希表记录访问过的节点。如果遇到已访问的节点，说明有环。
代码实现
/**
* @param {ListNode} head
* @return {boolean}
*/
function hasCycle(head) {
const visited = new Set();
let curr = head;
while (curr !== null) {
if (visited.has(curr)) {
return true;
}
visited.add(curr);
curr = curr.next;
}
return false;
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)