141. 环形链表

• 题目
• 法一、快慢指针
• 法二、哈希表

题目

• 给你一个链表的头节点 head ，判断链表中是否有环。

  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置 （索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
  如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

法一、快慢指针

• 快慢指针，如果有环快指针必定会追上慢指针

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        f=s=head#定义快慢指针，指向链表头节点
        while f and f.next:#当快指针和快指针的下一个都不为空时执行
            s=s.next#慢指针走一步
            f=f.next.next#快指针走两步
            if s==f:#如果快指针节点的值等于慢指针节点的值
                return True#说明有环
        return False

• 注意循环的条件，f快指针比s慢指针先到尾，所以不用判断s;只有保证f.next不为0才可以在循环中实现f=f.next.next
• if s==f不是（if s.val==f.val）比较的是节点本身，而不是节点的值。

法二、哈希表

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 1. python map
        m = {}   #创建一个空的哈希表 m，用于存储链表节点
        while head: 
            if m.get(head):  #检查哈希表中是否存在键为 head 的项
                return True  #如果存在，表示链表中存在环，返回 True。
            m[head] = 1  #如果不存在，将 head 作为键，值为 1 存入哈希表 m 中，表示已经访问过该节点。
            head = head.next   #更新为下一个节点
        return False