1.題目描述
給定一個(gè)鏈表咽安，判斷鏈表中是否有環(huán)雇卷。
為了表示給定鏈表中的環(huán)，我們使用整數(shù)pos來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）崎淳。 如果 pos 是 -1柜与，則在該鏈表中沒有環(huán)。
示例1:
輸入：head = [3,2,0,-4],pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)悄蕾，其尾部連接到第二個(gè)節(jié)點(diǎn)票顾。
示例2:
輸入：head = [1,2],pos = 0
輸出：true
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)帆调。
示例3:
輸入：head = [1],pos = -1
輸出：false
解釋：鏈表中沒有環(huán)奠骄。
2.分析
- 想到使用兩個(gè)指針
slow和fast分別遍歷鏈表，fast指針遍歷的速度是slow的兩倍番刊，如果兩個(gè)指針能重疊含鳞，就說明這個(gè)鏈表是有環(huán)的。 - 注意點(diǎn)如何判斷重疊芹务？
is是python中判斷兩個(gè)對(duì)象是否是同一個(gè)對(duì)象（內(nèi)存地址一致）蝉绷，所以可以用is來判斷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)佳晶，說明鏈表有盡頭桅狠，無環(huán)
try: # 用來規(guī)避fast.next 就是none這個(gè)情況
slow = slow.next
fast = fast.next.next
if slow is fast: # 這一步是關(guān)鍵，可以通過is來判斷節(jié)點(diǎn)是不是在同一個(gè)內(nèi)存地址里（也就是是否是同一個(gè)）
return True
except:
return False
return False
- 或者直接這么寫
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
