141 环形链表

佚名 4年前 (2020-07-20) Python 755人围观抢沙发百度已收录

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
# 快慢指针的做法，定义两个指针，一个走一步，一个走两步
# 如果他们不相遇的话，那就是没有环，如果在某一时刻相遇，
# 就说明是有环的。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 定义快慢指针都指向头部指针
        low,fast = head,head
        # 这样可以很快速的判断是否有环
        while low and fast and fast.next:
            # 慢指针走一步，快指针走两步
            low = low.next
            fast = fast.next.next
            # 快慢指针相遇，返回真
            if low == fast:
                return True
        return False