141_环形链表

类型：链表

• 141. 环形链表 💚

  https://leetcode-cn.com/problems/linked-list-cycle/

  ❓ 判断链表中是否有环

  💡 快慢指针

  class Solution:
      def hasCycle(self, head: ListNode) -> bool:
          if not head or not head.next:
              return False
  
          slow = head
          fast = head.next
  
          while slow != fast:
              if not fast or not fast.next:
                  return False
              slow = slow.next
              fast = fast.next.next
  
          return True

  时间复杂度：O(n)，空间复杂度：O(1)

  💡 哈希

  遍历的过程中将结点地址存入哈希，如果遍历过程中遇到已经存入哈希的结点，则说明成环。

  class Solution:
      def hasCycle(self, head: ListNode) -> bool:
          seen = set()
          while head:
              if head in seen:
                  return True
              seen.add(head)
              head = head.next
          return False

  时间复杂度：O(n)，空间复杂度：O(n)