題目

????????給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。如果存在環 ，則返回 true 。 否則，返回 false 。

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

????????示例：

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

快慢指針法

????????快慢指針法，也叫Floyd判圈法，是解決鏈表中環檢測問題的經典算法。其核心思想是使用兩個指針，一個快指針每次移動兩個節點，一個慢指針每次移動一個節點。如果鏈表中存在環，快慢指針最終會在環中的某一點相遇。若不存在環，快指針會先到達鏈表尾部。使用快慢指針法求解本題的主要步驟如下。

????????1、初始化指針。開始時，定義兩個指針，一個快指針（fast）和一個慢指針（slow），均指向鏈表的頭節點。

????????2、移動指針。每次迭代時，慢指針（slow）向前移動一步，快指針（fast）向前移動兩步。如果鏈表中存在環，由于快指針移動速度是慢指針的兩倍，最終快指針會追上慢指針。

????????3、終止條件。如果鏈表中沒有環，快指針會首先到達鏈表的尾部（None），這時可以確定鏈表無環。相反，如果快慢指針相遇，則表明鏈表中存在環。

????????根據上面的算法步驟，我們可以得出下面的示例代碼。

class ListNode:def __init__(self, x):self.val = xself.next = Nonedef create_linked_list(length, pos = -1):if length < 1 or (pos != -1 and (pos < 0 or pos >= length)):return Nonehead = ListNode(0)current = headcycle_node = Nonefor i in range(1, length + 1):new_node = ListNode(i)current.next = new_nodecurrent = new_nodeif i == pos + 1:cycle_node = new_node# 只有當pos有效且不為-1時，才創建環if cycle_node:current.next = cycle_node# 返回真正的頭節點，忽略初始的0節點return head.nextdef has_cycle_fast_slow_pointer(head):if head is None or head.next is None:return Falseslow = headfast = head.nextwhile fast is not None and fast.next is not None:if slow == fast:return Trueslow = slow.nextfast = fast.next.nextreturn False# 創建有環鏈表
head_with_cycle = create_linked_list(4, 1)
# 輸出: True
print(has_cycle_fast_slow_pointer(head_with_cycle))# 創建無環鏈表
head_no_cycle = create_linked_list(4, -1)
# 輸出: False
print(has_cycle_fast_slow_pointer(head_no_cycle))

哈希表法

????????哈希表法利用數據結構中的哈希表來記錄每個訪問過的節點。由于哈希表的查找效率非常高，平均時間復雜度為O(1)，故我們可以在遍歷鏈表的同時，將每個訪問過的節點添加到哈希表中。當發現某個節點已經被訪問過，即該節點存在于哈希表中時，則可斷定鏈表中存在環。使用哈希表法求解本題的主要步驟如下。

????????1、初始化。創建一個空的哈希表，在Python中，通常是集合set。

????????2、遍歷鏈表。從鏈表頭開始遍歷，對于每一個訪問到的節點，執行以下操作。

????????（1）檢查當前節點是否已經在哈希表中。

????????（2）如果不在，將當前節點添加到哈希表中，并繼續遍歷下一個節點。

????????（3）如果在哈希表中發現了當前節點，說明存在環，直接返回True。

????????3、遍歷結束。如果遍歷完整個鏈表都沒有發現重復的節點，則說明鏈表中沒有環，返回False。

????????根據上面的算法步驟，我們可以得出下面的示例代碼。

def has_cycle_hashset(head):visited_nodes = set()while head is not None:# 如果節點已經在集合中，說明有環if head in visited_nodes:return Truevisited_nodes.add(head)head = head.next# 遍歷結束，沒有發現環return False# 創建有環鏈表
head_with_cycle = create_linked_list(4, 1)
# 輸出: True
print(has_cycle_hashset(head_with_cycle))# 創建無環鏈表
head_no_cycle = create_linked_list(4, -1)
# 輸出: False
print(has_cycle_hashset(head_no_cycle))

總結

????????快慢指針法不需要額外的空間，時間復雜度為O(n)，其中n是鏈表中的節點數量。哈希表法則提供了另一種思路，雖然它需要額外的O(n)空間，但優點是實現直觀，易于理解和編碼。

????????在實際應用中，如果對空間復雜度有嚴格要求，推薦使用快慢指針法。如果空間不是問題，而對代碼的簡潔性和直觀性有更高要求，哈希表法也是一個不錯的選擇。

💡 如果想閱讀最新的文章，或者有技術問題需要交流和溝通，可搜索并關注微信公眾號“希望睿智”。