Given a linked list, determine if it has a cycle in it.

這個篇章開頭就問了這麼一個問題，【給一個鏈結陣列，判斷它是否有環】，意思是說在鏈結陣列中的某個節點，它指向的下一個節點是之前的節點，形成了一個循環結構；如果鏈結陣列中存在這樣的循環，就稱為帶環鏈表，反之則稱為無環鏈表。

而我們要怎麼判斷一個鏈結陣列中有沒有循環，這裡給了一個解法 — 使用【雙指針技巧】。

快慢指針算法

快慢指針算法又稱為龜兔賽跑算法，是雙指針技巧之一，原理是使用一個慢指針(slow pointer)和一個快指針(fast pointer)，慢指針一次往前移動一個索引，快指針一次往前移動兩個索引，這時會有兩個狀況：

1. 如果是帶環鏈表，快指針會追上慢指針。
2. 如果是無環鏈表，快指針會先到達鏈結陣列的尾端。

複雜度分析

簡單練習一下複雜度分析，當我們只使用指標進行操作，並沒有使用其他空間，我們的空間複雜度為O(1)。

而時間複雜度的計算就比較複雜，我們需要考慮會遇到的兩種情況：

1. 如果是帶環鏈表，快指針需要M次移動才會追上慢指針，M 為循環結構的長度。
2. 如果是無環鏈表，快指針需要N/2次移動才會抵達練結陣列的尾端，N 為鏈結陣列的長度。

在這兩種情況下，我們可以得出M≤N，最糟的情況下需要循環N次就能得出結果，因此這個算法的時間複雜度為O(n)。

小結

簡單講解了快慢指針算法和複雜度分析，快慢指針算法在陣列篇章時也有使用過，算是很常使用的一種演算法；而複雜度分析則是作為後端工程師應該提升的分析能力之一，不能什麼事情都使用暴力解，或是隨便找個套件能用就用，在某些情境下這樣反而會得到反效果。