题解 | #判断链表中是否有环#

两种方法可以解决

• HASH 表
  如果链表中指针在 HASH 表中出现过则表示有环，否则无环

  class Solution:
    def hasCycle(self , head ):
        # 时间复杂度 O(n)
        # 空间复杂度 O(n)
        has = set()
        while head:
            if head in has:
                return True
            has.add(head)
            head = head.next
        # 遍历完链表没有找到
        return False

• 快慢指针

  class Solution:
    def hasCycle(self , head ):
        # 时间复杂度 O(n)
        # 空间复杂度 O(1)
        if not head or not head.next:
            return False
        slow, fast = head, head.next
        while slow != fast:
            if not fast or not fast.next:
                # 如果 fast 或则 fast.next 为链表末尾了
                return False
            slow = slow.next
            fast = fast.next.next
        return True