Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Constraints:
- The number of the nodes in the list is in the range
[0, 104]. -105 <= Node.val <= 105posis-1or a valid index in the linked-list.
Follow up: Can you solve it using O(1) (i.e. constant) memory?
SOL：
暴力法：一個一個比對是否已經放在 nodeSet 裡面。
但我把 nodeSet 印出來發現會有這個，ListNode 好像會自己偵測到有沒有環(cycle)。
參考別人暴力法的寫法，是用dictionary+id()的方法，不過兩者的執行時間跟記憶體用量都差不多。
dictionary+id()的方法：141. Linked List Cycle [easy] (Python)
id()用法：用於返回对象的内存地址。
更好的方法是用快慢指針的方式，當快指針被慢指針追上，就代表有環。
參考影片：LeetCode 141. Linked List Cycle - 花花酱 刷题找工作 EP20
需要注意的是，除了要確認 fast 不是 None，也必須確認 fast.next 不是 None，因為fast.next 是 None 的時候，是不會有 next 的。
烘焙 (2)