力扣(leetcode) 141. 環形連結清單 (普通法) (快慢指針法--圖解)

題目在這：​​https://leetcode-cn.com/problems/linked-list-cycle/​​

思路分析:

注意：本題的環判斷一定要看指針是否已經出現過，即指針位址值，而不是看指針所指的值是否出現過。

法一:

是以我們建立一個清單，吧指針存進去，當發現目前周遊的指針已經在清單裡了。說明有環。

完整代碼

def hasCycle(self, head: ListNode) -> bool:
        res = []
        while head:
            if head in res:
                return True
            else:
                res.append(head)
                head = head.next      

當然。上述方法雖然能通過leetcode。但是空間複雜度不符合題目要求。

法二：

設定一快一慢兩個指針，如果有環，則兩個指針一定會在後面的某個位置重合。

快指針就像汽車。慢指針就像自行車，

看圖！！

def hasCycle(self, head: ListNode) -> bool:
        fast = head
        slow = head
        while fast and fast.next:# 由于快指針要移動兩次，是以判斷。fast.next是否為空。空則沒有next屬性。
            
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True