给你一个链表的头节点 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 解释:链表中没有环。
提示:
- 链表中节点的数目范围是
[0, 104]
-105 <= Node.val <= 105
pos
为-1
或者链表中的一个 有效索引 。
进阶:你能用 O(1)
(即,常量)内存解决此问题吗?
解题方法
法1:哈希表+单指针
以set数据结构作为散列表,存储访问过的节点;
循环遍历链表,记录访问过的节点;
在循环中判断当前节点是否已记录在散列表中,如果有,则为环状链表。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: visited = set() # 创建哈希表用以记录遍历经过的节点 temp = head # 指针指向head while temp: # 循环便利链表 if temp in visited: # 判断是否访问过当前节点 return True visited.add(temp) # 记录访问过的节点 temp = temp.next # 移动节点 return None
法2:双指针(快慢指针)
一快一慢两个指针,慢指针一次走1,快指针一次走2;
以相对速度考虑,如果有环,则一定会相遇;
注意循环条件,判断条件的设计。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: # 定义快慢指针,同时从起点head开始 slow = fast = head # 注意判断条件:fast, fast.next都不为None,才能循环 # fast.next不为 None,也是为了使 fast.next.next 能够被定义 while fast and fast.next: slow = slow.next # 慢指针,一次走1 fast = fast.next.next # 快指针,一次走1 if slow is fast: # 如果发生相遇,说明存在环 return True return False # 退出循环,说明fast或fast.next有 None, 即无环
标签:leetcode141,head,环形,fast,next,链表,节点,指针 From: https://www.cnblogs.com/chenxiaomeng/p/18072893