題目

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

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

????????示例：

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

快慢指針法

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

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

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

????????3、終止條件。如果鏈表中沒有環(huán)，快指針會(huì)首先到達(dá)鏈表的尾部（None），這時(shí)可以確定鏈表無環(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# 只有當(dāng)pos有效且不為-1時(shí)，才創(chuàng)建環(huán)if cycle_node:current.next = cycle_node# 返回真正的頭節(jié)點(diǎn)，忽略初始的0節(jié)點(diǎn)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é)構(gòu)中的哈希表來記錄每個(gè)訪問過的節(jié)點(diǎn)。由于哈希表的查找效率非常高，平均時(shí)間復(fù)雜度為O(1)，故我們可以在遍歷鏈表的同時(shí)，將每個(gè)訪問過的節(jié)點(diǎn)添加到哈希表中。當(dāng)發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)已經(jīng)被訪問過，即該節(jié)點(diǎn)存在于哈希表中時(shí)，則可斷定鏈表中存在環(huán)。使用哈希表法求解本題的主要步驟如下。

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

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

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

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

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

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

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

def has_cycle_hashset(head):visited_nodes = set()while head is not None:# 如果節(jié)點(diǎn)已經(jīng)在集合中，說明有環(huán)if head in visited_nodes:return Truevisited_nodes.add(head)head = head.next# 遍歷結(jié)束，沒有發(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))

總結(jié)

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

????????在實(shí)際應(yīng)用中，如果對(duì)空間復(fù)雜度有嚴(yán)格要求，推薦使用快慢指針法。如果空間不是問題，而對(duì)代碼的簡(jiǎn)潔性和直觀性有更高要求，哈希表法也是一個(gè)不錯(cuò)的選擇。

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