｜環形鏈表

給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。

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

如果鏈表中存在環，則返回 true 。 否則，返回 false 。

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

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

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

｜ 題解

思路及算法
本方法需要讀者對「Floyd 判圈算法」（又稱龜兔賽跑算法）有所了解。
假想「烏龜」和「兔子」在鏈表上移動，「兔子」跑得快，「烏龜」跑得慢。當「烏龜」和「兔子」從鏈表上的同一個節點開始移動時，如果該鏈表中沒有環，那么「兔子」將一直處于「烏龜」的前方；如果該鏈表中有環，那么「兔子」會先于「烏龜」進入環，并且一直在環內移動。等到「烏龜」進入環時，由于「兔子」的速度快，它一定會在某個時刻與烏龜相遇，即套了「烏龜」若干圈。
我們可以根據上述思路來解決本題。具體地，我們定義兩個指針，一快一滿。慢指針每次只移動一步，而快指針每次移動兩步。初始時，慢指針在位置 head，而快指針在位置 head.next。這樣一來，如果在移動的過程中，快指針反過來追上慢指針，就說明該鏈表為環形鏈表。否則快指針將到達鏈表尾部，該鏈表不為環形鏈表。

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def hasCycle(self, head: ListNode) -> bool:# 如果鏈表為空或者只有一個節點 直接返回Falseif head is None or head.next is None:return False# 定義快慢指針fast = headslow = head# 先讓快指針走一步fast = fast.nextwhile fast:# fast指針追上了slow指針 證明有環if fast == slow:return Trueelse:# 特殊情況處理，任何一個節點的next節點is None 都可以認為此鏈表無環if fast.next is None:return Falsefast = fast.next.nextslow = slow.nextreturn False

總結

以上是生活随笔為你收集整理的python 环形链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。