环形链表
难度:
标签:
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 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, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
代码结果
运行时间: 60 ms, 内存: 18.5 MB
/*
* 思路：Java Stream API 不直接支持链表操作，但我们可以通过转换为 Collection 并使用 Set 来检测环。
* 这里不使用 Stream，而是用 HashSet 来检测循环引用。
*/
import java.util.HashSet;
import java.util.Set;
public class Solution {
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<>();
while (head != null) {
if (seen.contains(head)) {
return true;
}
seen.add(head);
head = head.next;
}
return false;
}
}解释
方法:
本题解使用了快慢指针的思路。初始化两个指针slow和fast，它们都指向链表的头节点。接下来，slow指针每次移动一步，fast指针每次移动两步。如果链表中存在环，那么fast和slow最终会在环中的某个节点处相遇。while循环的条件是fast和fast.next都不为None，这样可以防止fast指针越界。如果fast和slow相遇，说明链表中有环，返回True；如果fast或fast.next为None，说明到达了链表的尾部，链表中不存在环，返回False。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在解决此问题时，为什么选择使用快慢指针而不是其他数据结构如哈希表来检测环？
▷🦆
快慢指针策略中，fast指针为什么选择每次移动两步而不是三步或更多？
▷🦆
如果快指针追上慢指针，这是否确实意味着链表中一定存在环，还是有其他可能的情况？
▷🦆
什么情况下会导致`fast.next`或`fast`变成`None`？这种情况是否表明链表一定没有环？
▷相关问题
环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？