141. Linked List Cycle

Easy

Description

給定一個鏈結串列的頭節點 head，判斷該鏈結串列是否存在環。如果串列中某個節點可以再次被訪問到，則存在環。

Example:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: 串列中有一個環，尾節點連接到第 1 個節點

Intuition#

核心思路：快慢指針（Floyd’s Cycle Detection）– 如果有環，快指針終會追上慢指針。

如果沒有環，快指針會先到達 null
如果有環，快指針在環中會像跑道上的跑者一樣追上慢指針
每次迭代快慢指針的距離縮小 1，所以一定會相遇

Approaches#

1: HashSet#

概念: 將訪問過的節點存入 HashSet，如果遇到已存在的節點，說明有環
時間複雜度: O(n) - 最多遍歷所有節點
空間複雜度: 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)#

概念: 慢指針每次走 1 步，快指針每次走 2 步。若有環則兩者必會相遇；若無環則快指針先到 null
時間複雜度: O(n) - 最多遍歷兩倍節點數
空間複雜度: 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
    }
}

注意使用參照相等 === 而非結構相等 ==，因為我們要比較的是同一個節點物件，不是節點的值。

🔑 Takeaways#

Pattern: Floyd’s Cycle Detection 是偵測環的經典演算法，也是 LeetCode 142（找環的起點）的基礎
關鍵技巧: 快慢指針不只能偵測環，還能找中點、找倒數第 k 個節點，是鏈結串列的瑞士刀