從LeetCode學演算法 - 31 Linked List (4)

0141. Linked List Cycle (Easy)

Question

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

分析/解題

給定一個Linked List，試檢查其是否含有一個環(Cycle) 在裡面。
我們有一小段時間沒有講Linked List，這邊不再贅述其基礎特性，
想要複習的讀者可以參閱第4篇的說明。

當我們在考慮這個題目的時候，會留意到兩個特性：

這個Linked List是指Single Linked List(也就是指向的方向只有單向)。
如果有環的話，應該會從最後一個節點再連接到前面的節點。
(從中間的話就會產生分歧的狀況)

在以上的特性狀況下，假設有一個環在Linked List中的話，
取一個節點從head開始不斷往其next走，會先經過最後一個節點，
接著再接回到前面某個節點再往下走，這樣會是一個循環；
更重要的是，顯然一進入這個環中，接下來就會一直在環內移動 。
(因為走到尾端又會再接回來)

這裡我們引入一個蠻常用的解題方式：設定快速和慢速的指標 。
我們讓fast和slow先設定在head的位置，每次fast走兩步，slow走一步 ，
它們就像是國小時針分針追趕的感覺一樣。

接下來我們可以將狀況分成以下兩種：

假設有環的狀況，
不管走多快多慢都會陷入這個環內 ，
所以會變成每次fast多走了一步，這一步用來追趕slow 。
因為slow也沒別的地方可以躲，所以fast每次多走一步一定可以趕得上
(也因為一步一步趕所以沒有追上卻錯開的可能)。
因此，我們知道fast和slow最終會來到相同的位置(也就是兩者相等 )
假設沒有環 的狀況，
由於不會重複，故最終fast一定會先走到尾端 ，最後看到NIL 。

故我們要做的事情很簡單，只要先設定fast跟slow，
在它們沒有走到NIL之前，每次去檢查fast是否有追上slow。
追上的話就回傳true ，而如果看到fast的下一個節點是NIL 的話，
就代表走到盡頭了 ，此時應該要回傳false 。

整個演算的順序：

考量起始的狀況，我們必須先檢查head跟head.next 當中是否有NIL值
開始一個迴圈，
開始前讓fast被設定為fast.next.next，slow則被設定為slow.next 。
當fast還沒有遇到NIL前，每次各自走相應步數，再檢查兩者是否相等。
(相等表示有環 ，回傳true )
請注意：當fast和fast.next 都處於非NIL 的狀況時，迴圈才能夠執行。
當fast或fast.next是NIL的話：表示走到盡頭了！跳離迴圈後，
將其return false 以表示它當中並沒有環。

寫成程式碼大概如下面所示：

Java

Python這邊額外提供了LeetCode使用者 StefanPochmann 的做法，
這個做法使用了try…except來進行錯誤處理，
有興趣的讀者不妨試試看。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(1)
由於fast比slow每次多走一步，我們可預期在走環的部分時，為了相遇走的長度的複雜度為O(K)。那麼K最大也頂多就是囊括所有節點，
所以時間的複雜度最大就會取決於N 。
當然，還有另一種狀況是裡面沒有環 ，
時間複雜度也是O(N)。(走到底就結束了)
另外，我們沒有另外需要存下其他整個LinkedList的節點，所以僅有一些必要的節點被宣告，故空間複雜度為O(1))

相似及延伸：
1. ** 0142.** Linked List Cycle II

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~