Leetcode 141 與 Leetcode 142 題類似绑嘹，Leetcode 141 為判斷鏈表是否有環(huán)，而Leetcode 142在判斷若有環(huán)基礎上返回起始環(huán)的節(jié)點怠李。
- Leetcode 141：
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
分析： 設置一個快指針fast圾叼、一個慢指針slow。由于我們知道若有環(huán)捺癞，快慢指針將一直"跑"下夷蚊，沒有終點，并且快慢指針一定會相遇髓介；如同在沒有設置終點暫停的情況下惕鼓，兩人從同一起點出發(fā)以不同速度在環(huán)形跑道上跑步，跑得快的同學最終會出現(xiàn)比跑得慢的同學多跑一圈并且相遇的情形唐础。 這里設置為快指針跑兩步時箱歧，慢指針跑一步，兩者速度比為2:1一膨。
Python代碼：
class Solution(object):
def hasCycle(self, head):
fast = slow = head
while slow and fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
- Leetcode 142：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
分析：此題在 Leetcode 141的基礎上呀邢，添加了若有環(huán)即返回其環(huán)起始位置的步驟。同 Leetcode 141分析中所述豹绪，若設定快指針每跑兩步价淌，慢指針跑一步，兩者速度比為2:1瞒津，即在相同時間內蝉衣，兩者跑得距離之比也為2:1。如圖巷蚪，當有環(huán)時病毡，設置b點為環(huán)的起始位置，m點為快慢指針第一次相遇的位置屁柏，hb距離為x1啦膜，b到m距離為x2有送，m到b的距離為x3。由于同一起點出發(fā)功戚，在相同時間內兩者跑的距離之比為2:1娶眷，所以當他們在m點相遇時有 x1+x2+x3+x2 = 2(x1+x2)似嗤，即x1 = x3啸臀。
image
當快慢指針在m點相遇后，慢指針從m點出發(fā)烁落，head指針從h點同時出發(fā)并以相同的速度前行乘粒，由于x1=x3，因此兩者會在b點伤塌，即環(huán)的起始位置相遇灯萍。
Python代碼：
class Solution(object):
def detectCycle(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
while slow != head:
slow = slow.next
head = head.next
return head
return None
