前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >链表是否有环,视频讲解

链表是否有环,视频讲解

作者头像
double
发布2020-07-07 14:55:24
7010
发布2020-07-07 14:55:24
举报
文章被收录于专栏:算法channel

Day 40:判断链表是否有环

1 链表有环是什么意思?

在判断是否有环前,需要先知道什么是链表中的环?

如下所示的链表有5个节点组成,框内的数字代表编号,也可理解为节点的地址。注意区分地址值和链表的数据域是完全不同的:

节点0指向节点3,而节点10又指向节点3,所以节点3就是环的入口,形成如下所示的一个环:

如果像下面这样遍历一个有环链表:

代码语言:javascript
复制
# head 是链表的头
while head:
    print(head.data)
    head = head.next

程序将会进入死循环,会在环内无穷的跑下去。

所以,研究如何判断链表是否有环,是一个非常有意义的课题,也是面试中常考的。

2 如何判断链表是否有环

通过哈希的方法,代码比较好理解:

代码语言:javascript
复制
class Solution(object):
    def hasCycle(self, head):
        s = set()
        tmp = head
        while tmp:
            if tmp in s:
                return True
            s.add(tmp)
            tmp = tmp.next 
        return False

今天主要分析如何使用快慢指针判断链表是否有环,做到O(1)的空间复杂度,O(n)的时间复杂度,因此比哈希方法要更加节省内存空间。

快慢指针判断链表是否有环,代码其实非常清晰,但是理解背后的数学原理,才是真正写出代码的关键,也就说一旦理解原理,就会很自然的写出代码;相反,如果不理解,仅仅凭记忆,那么时间长了,就容易忘记,面试时就容易写错。

今天,重点也是理解背后的数学原理,下面这个视频参考网络,讲解的非常清晰,大家不妨看一遍:

代码网络上一搜有很多,在这里就不再贴了。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-07-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员郭震zhenguo 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Day 40:判断链表是否有环
    • 1 链表有环是什么意思?
    • 2 如何判断链表是否有环
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档