題目描述:判斷鏈結串列中是否存在環。
解題思路:Floyd 的龜兔賽跑演算法:slow 指標每次走一步,fast 指標每次走兩步。若存在環,fast 最終會追上 slow(在環內相遇);若無環,fast 會到達 null。這個方法只需 O(1) 空間,不需要記錄訪問過的節點。
時間複雜度:O(n) — fast 最多繞環一圈後就會追上 slow。
空間複雜度:O(1) — 只用兩個指標。
1. slow = fast = head 2. While fast != null and fast.next != null: a. slow = slow.next b. fast = fast.next.next c. If slow == fast: return true 3. Return false
雜湊集合 O(n) 時間,O(n) 空間:存儲訪問過的節點,若重複訪問則有環 — 直接但空間效率差。
遞迴深度計數:若深度超過 n,推斷有環 — 不可靠,取決於堆疊大小。