LeetCode题目（Python实现）：环形链表

清疚 2023-07-11 11:02 119阅读 0赞

文章目录

  • 题目
    • 自己的想法
      • 算法实现
      • 执行结果
      • 复杂度分析
    • 哈希表法
      • 执行结果
      • 复杂度分析
    • 小结

题目

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例1 :

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

在这里插入图片描述
示例2 :

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

在这里插入图片描述
示例3 :

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

在这里插入图片描述

自己的想法

算法实现

  1. class Solution:
  2.     def hasCycle(self, head: ListNode) -> bool:
  3.         if not (head and head.next):
  4.             return False
  5.         slow = head
  6.         fast = head.next
  7.         while fast.next and fast.next.next:
  8.             if slow == fast:
  9.                 return True
  10.             slow = slow.next
  11.             fast = fast.next.next
  12.         return False

执行结果

执行结果 : 通过
执行用时 : 52 ms, 在所有 Python3 提交中击败了77.58%的用户
内存消耗 : 16.8 MB, 在所有 Python3 提交中击败了19.14%的用户
在这里插入图片描述

复杂度分析

  • 时间复杂度：O(n)，
    我们只遍历了包含有 n 个元素的列表一次。
  • 空间复杂度：O(1)

哈希表法

  1. class Solution:
  2.     def hasCycle(self, head: ListNode) -> bool:
  3.         if head == None:
  4.             return False
  6.         target = {
  7.     head}
  8.         head = head.next
  9.         while head:
  10.             if head in target:
  11.                 return True
  12.             else:
  13.                 target.add(head)
  14.                 head = head.next
  15.         return False

执行结果

在这里插入图片描述

复杂度分析

  • 时间复杂度：O(n)，
    我们只遍历了包含有 n 个元素的链表一次。
  • 空间复杂度：O(n)，
    所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

小结

先按照自己的想法设计，用快慢指针的方法，当快指针和慢指针相遇时，说明有环，否则快指针会到达尾部从而跳出循环。之后学习了哈希表法，通过建立字典，一边遍历链表，一边查找并将节点加入字典中，由于哈希表查找时间复杂度低，所以会快很多。

发表评论

表情：
评论列表 （有 0 条评论，119人围观）

还没有评论，来说两句吧...

相关阅读