--- tags: 資訊科技產業, info2021 --- # 課堂模擬面試 - [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) 🧔 : interviewer 👶 : interviewee ## 題目描述 Given `head`, the head of a linked list, determine if the linked list has a cycle in it. ## Repeat 👶 : 給我一個指向 linked list 的 head 的指標，如果這個 linked list 有 cycle，程式要回傳 `true`，否則要回傳 `false`，這是題目想要的要求嗎? 🧔 : 是 👶 : 請問這個 linked list 是「單向」還是「雙向」? 🧔 : 這裡使用單向 linked list :::warning * Linked list 的題目要記得確認是單向或是雙向 ::: ## Example ![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png) 👶 : 圖中 node (-4) 接到已經存在的 node (2)，這是一個有 cycle 的 linked list；如果 node (-4) 指向 `null`，則這是一個沒有 cycle 的 linked list ## Approach - 1 👶 : 我想到的作法是，從 `head` 開始走訪整個 linked list，並順便將走訪過的 node 的位址儲存在一個 array 之中，之後走訪時順便檢查是否到達已經走訪過的 node，也就是發現 linked list 是有 cycle 的。 🧔 : 所以你是想利用額外的空間來完成這個程式嗎? 👶 : 是的 🧔 : 為了節省成本，我們會希望產品所配備的記憶體容量越小越好，以及在產品上運行的程式盡可能地避免使用額外的空間。 🧔 : 如果這題不使用額外的空間，你有別的做法嗎? ## Approach - 2 👶 : 如果不使用額外的空間，那我會想使用兩個 pointer 從頭走訪 linked list。像龜兔賽跑，其中一個 pointer 會走訪得比較快，也就是一次走訪兩個 node；另一個走訪較慢的 pointer 則是一次走訪一個 node 如果 linked list 有 cycle，那就會像在操場上賽跑，走訪較快的 pointer 會再度與走訪較慢的 pointer 相遇 如果 linked list 沒有 cycle，則是像直線賽跑，走訪較快的 pointer 會先到達終點，也就是 `null` ## Code - 1 👶 : 我先定義兩個 pointer，走訪較快的命名為 `fast`，走訪較慢的命名為 `slow`，他們的起點都在 `head` ```c= bool hasCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; ``` 👶 : 接著，要讓兩個 pointer 開始走訪，這裡利用 while 迴圈，終止條件是 `(fast && fast->next)` 前面的 `fast` 代表當較快的 pointer 到達 `null` 時，代表 linked list 沒有 cycle，不用再進入迴圈了 後面的 `fast->next` 則是代表較快的 pointer 在一次走訪兩個 node 的過程中，就已經到達 `null` 了 ```c=4 while (fast && fast->next) { ``` 👶 : 在迴圈中，如果發現 `fast` 和 `slow` 相遇了，代表 linked list 有 cycle，回傳 `true` 結束程式 ```c=5 if (fast == slow) { return true; } ``` 👶 : 若兩個 pointer 還沒相遇，就讓兩個 pointer 跨下一步 : `fast` 到下下個 node，`slow` 到下一個 node ```c=8 fast = fast->next->next; slow = slow->next; ``` 👶 : `fast` 到達(或預計到達) `null` 時會跳出 while 迴圈，代表 linked list 沒有 cycle，回傳 `false`，結束程式 ```c=10 } return false; } ``` ## Test - 1 ```shell 1 -> 2 -> null ``` 🧔 : 在上述的測試結果出現錯誤了，請問要如何改正你的程式? ## Code - 2 👶 : 應該將 「讓 `fast` 和 `slow` 走下一步」 先於 「檢查 `fast` 和 `slow` 兩者是否相遇」 之前執行 ```c= bool hasCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; while (fast && fast->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) { return true; } } return false; } ``` ## Test - 2 * [Submission Detail](https://leetcode.com/submissions/detail/616199073/) ## Optimization 🧔 : 是否能再寫出更簡短的程式嗎?