給定一個鏈結串列的頭節點
head，判斷該鏈結串列是否存在環。如果串列中某個節點可以再次被訪問到，則存在環。
Example:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: 串列中有一個環，尾節點連接到第 1 個節點
Intuition
TIP
核心思路：快慢指針（Floyd’s Cycle Detection）— 如果有環，快指針終會追上慢指針。
- 如果沒有環，快指針會先到達 null
- 如果有環，快指針在環中會像跑道上的跑者一樣追上慢指針
- 每次迭代快慢指針的距離縮小 1，所以一定會相遇
Approaches
1. HashSet — O(n) / O(n)
- Idea: 將訪問過的節點存入 HashSet，如果遇到已存在的節點，說明有環
- Time:
O(n)- 最多遍歷所有節點 - Space:
O(n)- HashSet 儲存所有節點
class Solution {
fun hasCycle(head: ListNode?): Boolean {
val visited = HashSet<ListNode>()
var curr = head
while (curr != null) {
if (!visited.add(curr)) return true
curr = curr.next
}
return false
}
}⭐ 2. Floyd's Cycle Detection (Fast & Slow Pointers) — O(n) / O(1)
- Idea: 慢指針每次走 1 步，快指針每次走 2 步。若有環則兩者必會相遇；若無環則快指針先到 null
- Time:
O(n)- 最多遍歷兩倍節點數 - Space:
O(1)- 只用兩個指針
class Solution {
fun hasCycle(head: ListNode?): Boolean {
var slow = head
var fast = head
while (fast?.next != null) {
slow = slow?.next
fast = fast.next?.next
if (slow === fast) return true
}
return false
}
}WARNING
注意使用參照相等 === 而非結構相等 ==，因為我們要比較的是同一個節點物件，不是節點的值。
🔑 Takeaways
- Pattern: Floyd’s Cycle Detection 是偵測環的經典演算法，也是 LeetCode 142（找環的起點）的基礎
- Key trick: 快慢指針不只能偵測環，還能找中點、找倒數第 k 個節點，是鏈結串列的瑞士刀