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）→ 无环 } }

细节补充

1. while (fast != null && fast.next != null)

   • fast != null：防止兔子自己踩空（当前节点不能是null）。

   • fast.next != null：防止兔子走第二步时踩空（要取fast.next.next，必须保证fast.next存在）。
     如果链表无环，兔子最先触碰到null，循环就结束了。

2. fast = fast.next.next;
   兔子走两步，因为前面已经保证了fast和fast.next非空，所以这一步安全。

3. if (fast == slow) return true;
   比较的是两个引用是否指向同一个节点对象。如果相遇，说明兔子在环内追上了乌龟。

复杂度

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

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

  ---

3. 相关知识补充

1. Set接口和HashSet类

   • Set不包含重复元素，允许最多一个null。

   • HashSet基于哈希表，add、contains、remove都是 O(1)。

2. add方法的返回值

   • boolean add(E e)：如果集合尚未包含e，添加并返回true；如果已包含，返回false。

3. 对象的相等性

   • 默认情况下，HashSet使用hashCode()和equals()来判断两个对象是否相同。

   • ListNode没有重写这两个方法，因此比较的是内存地址，正好是我们需要的“是不是同一个节点”。