給定一個鏈表霞揉，返回鏈表開始入環(huán)的第一個節(jié)點雄家。 如果鏈表無環(huán)朽基，則返回 null昭伸。
為了表示給定鏈表中的環(huán)梧乘，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1庐杨，則在該鏈表中沒有環(huán)选调。
說明：不允許修改給定的鏈表。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環(huán)辑莫，其尾部連接到第二個節(jié)點学歧。
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環(huán)罩引，其尾部連接到第一個節(jié)點各吨。
示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)。
- show the code:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
### code1
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dic = {None}
while head:
if head not in dic:
dic.add(head)
head = head.next
else:
return head
### code2
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return head
slow,quick = head,head
iscycle = False
while quick.next and quick.next.next:
slow = slow.next
quick = quick.next.next
if quick == slow:
iscycle = True
break
if iscycle:
pointer1 = head
pointer2 = slow
while pointer1 != pointer2:
pointer1 = pointer1.next
pointer2 = pointer2.next
return pointer1
else:
return None
- 此題是上一題環(huán)形鏈表的進階版
- 首先代碼一是常規(guī)方法哈希法袁铐，返回第一個重復(fù)出現(xiàn)的節(jié)點即可揭蜒。
- 代碼二的方法則比較有難度，其是根據(jù)一個規(guī)律：快慢指針同時從頭節(jié)點出發(fā)剔桨，若鏈表有環(huán)屉更，則一定會相遇，記錄下這個相遇的節(jié)點洒缀，重新放一個指針在此節(jié)點上瑰谜，一個指針在頭節(jié)點，兩者每次向前移動一步树绩，則他們倆一定會在環(huán)的入口相遇萨脑。
- 因此代碼二分為兩個步驟：第一步找出鏈表中快慢指針相遇的節(jié)點，同時也判斷了鏈表中是否有環(huán)饺饭，這里與上一題不同的是快慢指針的起點是相同的渤早。第二步則重新定位兩個指針，一個在上一步得到的相遇點處瘫俊，一個在頭節(jié)點處鹊杖，兩指針保持一樣的速度悴灵，他們相遇的節(jié)點則是我們的結(jié)果。
-
有關(guān)上面代碼二算法證明在官方題解里有詳細說明：
