leetcode_141. 环形链表

举报
悲恋花丶无心之人 发表于 2021/02/02 23:00:11 2021/02/02
【摘要】 目录 一、题目内容 二、解题思路 三、代码 一、题目内容 给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅...

目录

一、题目内容

二、解题思路

三、代码


一、题目内容

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

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false 。

进阶:

你能用 O(1)(即,常量)内存解决此问题吗?

示例 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 或者链表中的一个 有效索引 。

二、解题思路

快慢指针,若存在环,则快慢指针必定相遇。

三、代码


  
  1. # Definition for singly-linked list.
  2. class ListNode:
  3. def __init__(self, x):
  4. self.val = x
  5. self.next = None
  6. class Solution:
  7. def hasCycle(self, head: ListNode) -> bool:
  8. fast, slow = head, head
  9. while fast and fast.next:
  10. fast = fast.next.next
  11. slow = slow.next
  12. if fast == slow:
  13. return True
  14. return False
  15. if __name__ == '__main__':
  16. a = ListNode(3)
  17. a.next = ListNode(2)
  18. a.next.next = ListNode(0)
  19. a.next.next.next = ListNode(4)
  20. a.next.next.next.next = a.next
  21. s = Solution()
  22. ans = s.hasCycle(a)
  23. print(ans)

文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。

原文链接:nickhuang1996.blog.csdn.net/article/details/108972886

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。