# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# 這道題我們還是用雙指標的辦法，快指標f一次走兩步，慢指標s一次走一步，
# 如果兩個指標相遇，那么代表鏈表有環，不相遇就直接回傳好了，
# 下邊我們討論有環的情況下找到環的入口，
# 快慢指標第一次相遇的時候 f = 2s
# 假設鏈表長度為 a + b ，a為從頭部節點到環入口的長度，
# 那么f和s都走過一次a，f = a + n1*b , s = a + n2 * b
# n1一定是n2的倍數，
# f - s = (n1 - n2 ) b = s
# 我們讓 n = (n1 - n2) 可得 f = 2nb s=nb
# 我們觀察鏈表可以看到，如果我們從鏈表的頭部開始走，走到環的入口（需要完整走完鏈表）需要k步
# 那么 k = a + n3b # 這里n3 可以取任意整數，因此我們讓n3 為n
# k = a + nb 現在慢指標已經走了nb步了， 因此我們讓頭指標在走a步，就能夠和慢指標在環的入口相遇了，
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast,slow = head,head
while fast and slow and fast.next :
fast = fast.next.next
slow = slow.next
if fast == slow :
break
else:return
count = 0
while head != slow:
count += 1
head = head.next
slow = slow.next
return head
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/166172.html
標籤：Python