https://leetcode-cn.com/problems/linked-list-cycle/submissions/
判斷鏈表是否有環(huán) 可以使用hashmap來存儲是否之前有過
但是由于題目要求只能o1的空間復(fù)雜度
所以使用快慢指針來處理該問題
需要注意的幾點corner case,fast及slow node可能為空
如果有環(huán)則slow會追上fast, 如果沒有的話fast.next為空節(jié)點.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow = head
if not slow:
return False
fast = head.next
if not (fast and fast.next):
return False
while slow != fast and fast and fast.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
else:
return False
https://leetcode-cn.com/problems/linked-list-cycle-ii/
獲取環(huán)形鏈表的交叉位置鞋囊，一樣o1的空間復(fù)雜度
這里需要用一點證明
假設(shè)從最開始到交點的距離為x, fast和slow交點為y, 環(huán)剩下的距離為z
因為fast的速度是slow的一倍玫锋，所以fast的路徑長度為slow的的一倍
（x + y）* 2 = x + n(y + z) + y
左右都去掉一個x + y, 則可得 x + y = n(y + z)
x = (y + z)n - y
x = (n-1)(y+z) + z
由于我們知道y+z為一圈寝蹈，所以從相交點走z和從頭開始走x相遇的地方就位環(huán)的相交點
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
current = fast = slow = head
if not (fast and fast.next):
return
# 這里因為slow和fast一樣 所以需要先slow和fast都走一步再循環(huán)往前走
fast = fast.next.next
slow = slow.next
while fast != slow and fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast != slow:
return
while current != fast:
current = current.next
fast = fast.next
return current
