hot100---环形链表

141. 环形链表 – 力扣（LeetCode）

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false。

1. 方法一

思路

• 用 HashSet 充当“便利贴集合”。

• 遍历链表，每到一个节点，就试图把它放进 HashSet（贴上便利贴）。

• 如果放进去时发现它已经存在了（已经被贴上便利贴了），说明链表有环。

• 如果顺利走到了 null，说明链表没有环。

代码

/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/

/**
* 使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。
*/
public class Solution {
public boolean hasCycle(ListNode head) {
// 1. 创建一个哈希集合，用来存储“已经访问过”的节点
Set<ListNode> seen = new HashSet<>();

// 2. 遍历链表
while (head != null) {
// 3. 尝试把当前节点加入集合
// add() 方法会返回 boolean：
// – 如果集合中还没有这个节点，添加成功，返回 true
// – 如果集合中已经有了这个节点，添加失败，返回 false
if (!seen.add(head)) { // !true = false，不加；!false = true，进入 if
return true; // 节点重复出现 → 有环！
}
// 4. 移动到下一个节点
head = head.next;
}

// 5. 走到链表末尾 (null) 都没发现重复节点 → 无环
return false;
}
}

细节补充

① Set<ListNode> seen = new HashSet<>();

• Set：一个不包含重复元素的集合。

• HashSet：Set 最常用的实现，底层是哈希表，增删查平均都是 O(1)。

• 这里存的不是节点的值，而是节点对象的引用（地址）。

• HashSet 比较对象时用的是 equals 和 hashCode，默认比较内存地址，所以能精确识别出同一个节点。 所以即使两个不同节点的值相同，也会被当成不同的节点，这正是我们需要的——我们要判断的是同一个节点被多次访问。

② if (!seen.add(head))

• add 方法：如果集合中还没有这个元素，就把它加进去并返回 true；如果已经有了，就什么都不做并返回 false。

• 所以 !seen.add(head) 的意思是：如果没有添加成功（即已经存在），就执行 return true，代表发现了环。

复杂度

• 时间复杂度：O(n) 每个节点最多访问一次（有环时，重复的那个节点被访问第二次时就会退出）。

• 空间复杂度：O(n) 最坏情况下需要存储所有节点的引用。

  ---

2. 方法二

思路：龟兔赛跑

• slow（乌龟）一次走 1 步。

• fast（兔子）一次走 2 步。

如果链表是直的（无环），兔子会先跑到终点（null），比赛结束。 如果链表中有圆圈（有环），兔子会在圈里不断跑，而且因为兔子的速度是乌龟的两倍，兔子一定会从后面追上乌龟，两者在圈内某个点相遇。

代码

public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head; // 乌龟和兔子同时从起点出发

while (fast != null && fast.next != null) { // 兔子能跑就继续
fast = fast.next.next; // 兔子走两步
slow = slow.next; // 乌龟走一步

if (fast == slow) { // 兔子追上乌龟 → 有环
return true;
}
}
return false; // 兔子跑到终点（null）→ 无环
}
}

细节补充

复杂度

• 时间复杂度：O(n) 无环时，兔子跑完全程；有环时，乌龟最多走一圈，兔子最多走两圈。总体上每个节点被访问常数次。

• 空间复杂度：O(1) 只用了两个额外指针，没有占用额外内存。

  ---

3. 相关知识补充