题目
-
给你一个链表的头节点 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