Problem#
題目給你一個單向鏈結串列(Singly linked-list)，問你有沒有存在環(Cycle)?
follow-up: 可以在 $\mathcal{O}(1)$ 空間複雜度達成?
想法#
-
直覺: 遍歷一次 linked-list，過程中維護一個 set 放每個點的 val，假如遇到重複的，則代表存在環，反之，則不存在環。
- 時間複雜度: $\mathcal{O}(n\log{n})$
- 空間複雜度: $\mathcal{O}(n)$ for set
-
Floyd 判圈算法 (龜兔賽跑算法): 一個走一步另一個走兩步，相遇則代表有環 (TODO: 補證明)