題目

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

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

????????示例：

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

快慢指針法

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

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

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

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

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

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時，才創(chuàng)建環(huán)if cycle_node:current.next = cycle_node# 返回真正的頭節(jié)點，忽略初始的0節(jié)點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# 創(chuàng)建有環(huán)鏈表
head_with_cycle = create_linked_list(4, 1)
# 輸出: True
print(has_cycle_fast_slow_pointer(head_with_cycle))# 創(chuàng)建無環(huán)鏈表
head_no_cycle = create_linked_list(4, -1)
# 輸出: False
print(has_cycle_fast_slow_pointer(head_no_cycle))

哈希表法

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

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

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

????????（1）檢查當前節(jié)點是否已經(jīng)在哈希表中。

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

????????（3）如果在哈希表中發(fā)現(xiàn)了當前節(jié)點，說明存在環(huán)，直接返回True。

????????3、遍歷結束。如果遍歷完整個鏈表都沒有發(fā)現(xiàn)重復的節(jié)點，則說明鏈表中沒有環(huán)，返回False。

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

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

總結

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

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

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