专栏首页用户1174862的专栏Leetcode 142. Linked List Cycle II
原创

Leetcode 142. Linked List Cycle II

Leetcode 142. Linked List Cycle II

地址:Leetcode 142. linked list Cycle II

问题描述:检测链表是否存在环,是的话返回环入口,否则返回None.

这道题有两个思路,一个是经典的快慢指针的思路,另外一个是利用hashMap来记住已经访问过的Node。

思路一:检测到环的时候,令慢指针指向head,然后fast 和 slow指针皆一次移动一个,到他们再次相遇的时候就是环的入口。

简单证明如下,来自Leetcode网友:

代码:

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return None
        slow,fast = head,head
        while(fast and fast.next):
            slow = slow.next
            fast = fast.next.next
            if (slow == fast):
                slow = head
                while(slow!=fast):
                    slow = slow.next
                    fast = fast.next
                return slow  #返回入口节点
        return None

思路二:利用一个hashMap当再次访问节点的时候就是环的入口。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        visited = {}
        p = head
        while(p):
            if visited.get(p) != None:
                return p
            else:
                visited[p] = True
            p = p.next
        return None

最后总结来自:will_duan博客

目前我遇到的主要有以下几点应用:

  • 如上面第一题,判断一个链表是否有环
  • 如上面第二题,求一个链表是否存在环,如果存在,则求出环的入口结点
  • 另一个应用是求链表是否存在环的变式,如给定两个链表A和B,判断两个链表是否相交,解决方法就是将A链表尾节点指向头结点形成一个环,检测B链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。
  • 求有序链表中求出其中位数,这种问题也是设置快慢指针,当快指针到底链表尾部的时候,慢指针刚好指向链表中间的结点。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 加拿大汽车协会推出机器学习算法Gen 2,预测故障并提前送达拖车

    加拿大汽车协会(CAA)表示,通过使用其内部开发的新的预测分析技术,它将能够在发生故障之前将拖车送到特定地点。

    AiTechYun
  • 话题 | 怎么看微博抽奖抽不出男性?

    结果中奖名单一公布,男网友们基本上都炸了,因为获奖名单上的男女比例竟然是1:112!

    AI研习社
  • 教程 | 仅需六步,从零实现机器学习算法!

    从头开始写机器学习算法能够获得很多经验。当你最终完成时,你会惊喜万分,而且你明白这背后究竟发生了什么。

    机器之心
  • 中国AI如何成为“头雁”?听专家怎么说

    科大讯飞董事长刘庆峰1 日对《环球时报》记者表示,人工智能未来将是对整个社会生产生活方式产生深刻变革的关键技术,这个技术将像水和电一样在社会生活的各个场景中无所...

    新智元
  • 论文造假被AI抓:机器学习检测出4000多论文造假,一年损失高达10亿美元

    今年6月,斯坦福大学微生物学家分析了2009-2016年发表在分子与细胞生物学(MCB)上的960篇论文,发现其中59篇(6.1%)含有“不适当的”重复图像,约...

    新智元
  • 资源 | 有没有必要把机器学习算法自己实现一遍?

    有很多小伙伴问过我这样的问题,有没有必要把机器学习算法自己实现一遍。那么今天的答案来了。往下看,自己领会,还有2个资源。

    zenRRan
  • 两年,从月入4K到40K,从来不是努力工作,而是不断跳槽

    这两年期间,经历了4次跳槽,学习→工作实践→跳槽,是我登上每一节楼梯的方式。当然,跳槽的前提是你新学的知识+工作经验,能让面试官觉得你值得这份工作。

    磐创AI
  • 均分纸牌(经典贪心)

    有N堆纸牌,编号分别为1,2,…,N。每堆上有若干张,但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌,然后移动。

    double
  • 爱奇艺蒙版AI:弹幕穿人过,爱豆心中坐

    作为(伪)AI 行业从业者,之心编辑部里的小伙伴们自认都能够以不错的置信度人工识别「人工智能与人工智障」。但是,当我把下面这张爱奇艺 app 的截图放在大家面前...

    机器之心
  • 架构必经之路2 - 熔断机制

    项目中要做一个熔断机制,预防对第三方的接口调用压力太大。下面我介绍下项目中用到的熔断机制。

    Jackson0714

扫码关注云+社区

领取腾讯云代金券