＜LeetCode天梯＞Day029環形連結清單（哈希表+雙指針） | 初級算法 | Python

以下為我的天梯積分規則：

每日至少一題：一題積分+10分

若多做了一題（或多一種方法解答），則當日積分+20分（+10+10）

若做了三道以上，則從第三題開始算+20分（如：做了三道題則積分-10+10+20=40；做了四道題則積分–10+10+20+20=60）

初始分為100分

若差一天沒做題，則扣積分-10分（周六、周日除外注：休息）

堅持！！！

初級算法

刷題目錄

連結清單

題幹

給你一個連結清單的頭節點 head ，判斷連結清單中是否有環。

如果連結清單中有某個節點，可以通過連續跟蹤 next 指針再次到達，則連結清單中存在環。 為了表示給定連結清單中的環，評測系統内部使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。如果 pos 是 -1，則在該連結清單中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了辨別連結清單的實際情況。

如果連結清單中存在環，則傳回 true 。 否則，傳回 false 。

示例1:

輸入：head = [3,2,0,-4], pos = 1

輸出：true

解釋：連結清單中有一個環，其尾部連接配接到第二個節點。

示例2:

輸入：head = [1,2], pos = 0

解釋：連結清單中有一個環，其尾部連接配接到第一個節點。

示例3:

輸入：head = [1], pos = -1

輸出：false

解釋：連結清單中沒有環。

哈希表

分析：

今年，有些累了，先吧架構搭在這裡吧！～

更新日志：2021/11/20

我隻最終隻需要判斷内部有沒有環，内部有一個pos，當為-1的時候則為沒有環，輸出false;相反，則輸出True。

其中我們可以先将連結清單的值放在一個list哈希表中，然後判斷目前的節點是否存在。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        hashmap = []
        while head:
            if  head in hashmap:
                return True
            hashmap.append(head)
            head = head.next
        return False      

哇，這個時間真的是感人呀！！！

注意上面用的是list，下面我們用集合來看看會不會快一些！~

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        hashmap = set()
        while head:
            if  head in hashmap:
                return True
            hashmap.add(head)
            head = head.next
        return False      

快了很多，有沒有，這就是set()的妙用啊！哈哈哈，下面咱們在用雙指針試試~

雙指針

使用一個快指針m和慢指針n，如果最終m和n相等，那麼就傳回True，否則，傳回False。

慢指針針每次走一步，快指針每次走兩步，如果相遇就說明有環，如果有一個為空說明沒有環。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 雙指針
        if not head:
            return False
        
        # 設定兩個指針快和慢
        fast = head
        slow = head
        while fast != None and fast.next != None:
            slow = slow.next    # 慢走一步
            fast = fast.next.next    # 快走兩步
            # 設定判斷，如果相遇則說明有環
            if fast == slow:
                return True
            # 否則False
        return False