題目

難度：★★☆☆☆
類型：鏈表

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。

示例

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

示例1

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。

示例2

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。

示例3

解答

我們用快慢指針解決這個(gè)問題：

1. 輸入為空，則一定不是環(huán)形鏈表；

2. 定義慢指針p1和快指針p2，每次分別走一步和兩步，如果快指針走到了鏈表結(jié)尾，說明不是鏈表不是環(huán)形；

3. 如果存在環(huán)形結(jié)構(gòu)，則快慢指針一定會(huì)相遇，返回True即可。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        if not head:            # 輸入為空，一定不是環(huán)形鏈表
            return False

        p1 = p2 = head          # 定義慢指針p1和快指針p2
        while p2 and p2.next:   # 如果快指針沒有走到鏈表結(jié)尾
            p1 = p1.next        # 慢指針走一步
            p2 = p2.next.next   # 快指針走兩步
            if p1 == p2:        # 如果快慢指針相遇
                return True     # 是環(huán)形鏈表
        return False            # 否則不是

如有疑問或建議，歡迎評論區(qū)留言~