1、今日题目:第141题—环形链表
2、题目要求如下:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
比如:
输入: 1 -> 2 -> 0 -> 5
输出:True
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle
3、代码及解题思路
# 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:
"""
思路:
一、考虑特殊情况:
1、head -> [] 返回false
2、head.next -> [] 返回false
二、一般情况:
采用快慢指针,fast比slow快走两步,此时出现以下情况:
1、不是环形链表,那么fast.next or fast.next.next is None
return False
2、是环形链表,那么肯定会相遇的,即slow == fast
return True
三、为什么fast要比slow快两步,而不是一步呢? 注:s -> 3 表示slow指针当前指向3节点,下列情况均是这个意思
1、s -> 3; f -> 2
2、s -> 2; f -> 0
3、s -> 0; f -> -4
4、s -> -4; f -> 2
5、s -> 2; f -> 0 此时情况等于步骤2,因为确实是有环的 要是判定有环的条件是slow == fast 那么显然无法完成
那么用快两步试试:
1、s -> 3; f -> 0
2、s -> 2; f -> 2
3、s -> 0; f -> -4
4、s -> -4; f -> 0
5、s -> 2; f -> 2 此时相等
四、实际编写遇到的问题:
迭代条件是什么? 因为出现 NoneType object has no attribute next
我错误迭代条件是:fast.next.next or fast.next
分析:
fast 可能出现的情况有哪些
1、如何链表仅仅只有两个元素且不无环的情况下,fast = head.next.next = None 显然我的条件不满足
2、当链表是长度为2n+1的情况且无环的情况下,fast总是会出现在2n+1的位置上,那么fast.next is None
n = 1, 2, 3, ...,所以需要加入fast.next条件
修改为:fast or fast.next 还是相同的错误
再次分析:
fast = head.next.next = None
1、将 or 改为 and,原因如下:
A or B 如果 A = False 那么 or 逻辑运算会继续执行B,显然会出错 None.next 不可能
A and B 如果 A = False 直接返回 False 只有 A = True 的情况下,才会继续执行B
最后修改为 fast and fast.next
"""
# method1 迭代
# iscycle = True
# if not head or not head.next:
# return not iscycle
# slow, fast = head, head.next.next
# while fast and fast.next:
# if fast is slow:
# return iscycle
# else:
# slow = slow.next
# fast = fast.next.next
# return not iscycle
# method2 hash表
hashset = set()
while head:
if head in hashset:
return True
hashset.add(head)
head = head.next
return False
4、收获
- 对于python基础语法了解不够深入,很多特性无法用上,比如集合,字典等特性
- 对于小地方问题,基础不扎实,比如 or 和 and 使用场景,什么时候是or 什么时候是and