一、題目描述

---

二、思路分析

這是鏈表題目中的經典問題，核心就是 如何判斷鏈表是否有環。
常見的兩種方法有：

1. 哈希表法：用一個集合存儲訪問過的節點，如果再次遇到相同節點說明有環。

   • 缺點：需要額外的空間，空間復雜度 O(n)。

2. 快慢指針法（Floyd 判圈算法）：通過兩個速度不同的指針在鏈表中移動，如果存在環，那么快指針一定會在環中追上慢指針。

   • 優點：只需常數空間，空間復雜度 O(1)。

   • 這也是本題的最優解。

你的代碼實現采用了第二種方法，也就是 快慢指針法。

---

三、代碼講解

下面是我的實現代碼：

public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head.next;while (slow != fast) {if (fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return true;}
}

1. 邊界條件

if (head == null || head.next == null) {return false;
}

如果鏈表為空，或者只有一個節點（且沒有環），那么顯然不可能存在環，直接返回 false。

---

2. 初始化快慢指針

ListNode slow = head;
ListNode fast = head.next;

• slow 每次走一步；

• fast 每次走兩步。
  這樣設計可以保證在有環的情況下，快指針一定會在環中追上慢指針。

---

3. 循環遍歷

while (slow != fast) {if (fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}
}

• 如果快指針走到 null，說明鏈表沒有環（因為如果有環，快指針永遠不會走到盡頭）。

• 如果 slow == fast，則說明快慢指針在環中相遇，即鏈表存在環。

---

4. 返回結果

最終，如果跳出 while 循環，說明 slow == fast，返回 true。

---

四、復雜度分析

• 時間復雜度：O(n)

  • 最壞情況下，快慢指針要遍歷鏈表的所有節點，復雜度為線性級別。

• 空間復雜度：O(1)

  • 只用了兩個指針變量，不需要額外存儲空間。

---

五、總結

• 本題是典型的 快慢指針 應用場景。

• 通過設置不同速度的指針來判斷是否存在環，大大節省了空間。

• 此題也是后續 環形鏈表 II（尋找環的入口節點）的基礎。

---

? 總結一句話：
在鏈表問題里，如果涉及到“是否存在環”，首先考慮快慢指針。