【算法】leetcode142. 環形連結清單 II（快慢指針）

問題來源

• 142. 環形連結清單 II（快慢指針）

給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。

為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。

說明：不允許修改給定的連結清單。

 

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：連結清單中有一個環，其尾部連接配接到第二個節點。


示例 2：

輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：連結清單中有一個環，其尾部連接配接到第一個節點。


示例 3：

輸入：head = [1], pos = -1
輸出：no cycle
解釋：連結清單中沒有環。

           

大佬解析

• 環形連結清單 II（雙指針法，清晰圖解）

代碼

"""
class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast