1.題目描述
給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。
為了表示給定鏈表中的環(huán)，我們使用整數(shù)pos來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）。 如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)。
示例1:
輸入：head = [3,2,0,-4],pos = 1
輸出：true
解釋?zhuān)烘湵碇杏幸粋€(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。
示例2:
輸入：head = [1,2],pos = 0
輸出：true
解釋?zhuān)烘湵碇杏幸粋€(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。
示例3:
輸入：head = [1],pos = -1
輸出：false
解釋?zhuān)烘湵碇袥](méi)有環(huán)。
2.分析
- 想到使用兩個(gè)指針
slow和fast分別遍歷鏈表，fast指針遍歷的速度是slow的兩倍，如果兩個(gè)指針能重疊，就說(shuō)明這個(gè)鏈表是有環(huán)的。 - 注意點(diǎn)如何判斷重疊？
is是python中判斷兩個(gè)對(duì)象是否是同一個(gè)對(duì)象（內(nèi)存地址一致），所以可以用is來(lái)判斷slow和fast指向的是不是同一個(gè)節(jié)點(diǎn)。 - 注意邊界條件的排除
3.解答
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
可以考慮用兩個(gè)指針，slow和fast，當(dāng)這兩個(gè)指針重疊之后，則表示這個(gè)鏈表有環(huán)
"""
if not head or not head.next:
return False
slow,fast = head,head
while slow and fast: # 如果跳出這個(gè)循環(huán)，說(shuō)明鏈表有盡頭，無(wú)環(huán)
try: # 用來(lái)規(guī)避fast.next 就是none這個(gè)情況
slow = slow.next
fast = fast.next.next
if slow is fast: # 這一步是關(guān)鍵，可以通過(guò)is來(lái)判斷節(jié)點(diǎn)是不是在同一個(gè)內(nèi)存地址里（也就是是否是同一個(gè)）
return True
except:
return False
return False
- 或者直接這么寫(xiě)
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
else:
return False
