leetcode中怎么判斷鏈表是否有環

LeetCode中怎么判斷鏈表是否有環

在LeetCode的算法題目中，鏈表是一個常見的數據結構。鏈表中的環（Cycle）是指鏈表的某個節點的next指針指向了鏈表中之前的某個節點，從而形成了一個環狀結構。判斷鏈表是否有環是一個經典的面試題，本文將詳細介紹如何在LeetCode中判斷鏈表是否有環，并分析常見的解題思路和算法。

1. 問題描述

給定一個鏈表，判斷鏈表中是否有環。如果鏈表中有某個節點可以通過連續跟蹤next指針再次到達，則鏈表中存在環。為了表示給定鏈表中的環，我們使用整數pos來表示鏈表尾連接到鏈表中的位置（索引從0開始）。如果pos是-1，則在該鏈表中沒有環。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環。

2. 解題思路

判斷鏈表是否有環的常見方法有兩種：哈希表法和快慢指針法。下面我們將分別介紹這兩種方法。

2.1 哈希表法

哈希表法的思路是遍歷鏈表中的每個節點，并將每個節點的引用存儲在哈希表中。如果在遍歷過程中發現某個節點的引用已經存在于哈希表中，則說明鏈表中存在環；否則，鏈表中沒有環。

算法步驟：

1. 初始化一個空的哈希表visited。
2. 遍歷鏈表中的每個節點：
   • 如果當前節點已經存在于visited中，則鏈表中存在環，返回true。
   • 否則，將當前節點添加到visited中。
3. 如果遍歷完整個鏈表都沒有發現重復的節點，則鏈表中沒有環，返回false。

代碼實現：

def hasCycle(head):
    visited = set()
    while head:
        if head in visited:
            return True
        visited.add(head)
        head = head.next
    return False

時間復雜度： O(n)，其中n是鏈表中的節點數。最壞情況下需要遍歷整個鏈表。

空間復雜度： O(n)，哈希表存儲了鏈表中的所有節點。

2.2 快慢指針法

快慢指針法是一種更高效的判斷鏈表是否有環的方法。該方法使用兩個指針，一個快指針和一個慢指針?？熘羔樏看我苿觾刹?，慢指針每次移動一步。如果鏈表中存在環，快指針最終會追上慢指針；如果鏈表中沒有環，快指針會到達鏈表的末尾。

算法步驟：

1. 初始化兩個指針slow和fast，都指向鏈表的頭節點head。
2. 使用一個循環遍歷鏈表：
   • 如果fast或fast.next為None，則鏈表中沒有環，返回false。
   • 否則，slow指針移動一步，fast指針移動兩步。
   • 如果slow和fast指針相遇，則鏈表中存在環，返回true。
3. 如果循環結束仍未相遇，則鏈表中沒有環，返回false。

代碼實現：

def hasCycle(head):
    if not head or not head.next:
        return False
    slow = head
    fast = head.next
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    return True

時間復雜度： O(n)，其中n是鏈表中的節點數。最壞情況下需要遍歷整個鏈表。

空間復雜度： O(1)，只使用了兩個額外的指針。

3. 算法比較

4. 總結

判斷鏈表是否有環是一個經典的算法問題，LeetCode中也有相關的題目。本文介紹了兩種常見的解題方法：哈希表法和快慢指針法。哈希表法簡單直觀，但需要額外的空間；快慢指針法空間復雜度低，效率高，但實現稍微復雜一些。在實際應用中，可以根據具體需求選擇合適的方法。

在LeetCode中，推薦使用快慢指針法來解決鏈表是否有環的問題，因為它不僅效率高，而且空間復雜度低，適合處理大規模數據。希望本文能幫助你更好地理解和掌握判斷鏈表是否有環的算法。