开发者社区> wangscaler> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

怒刷力扣(环形链表)

简介: 没想到曾经的寓言故事龟兔赛跑,还能应用在解循环的算法之中,今天是涨了见识了。
+关注继续查看

环形链表

WangScaler: 一个用心创作的作者。

声明:才疏学浅,如有错误,恳请指正。

题目

给你一个链表的头节点 head ,判断链表中是否有环。

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

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

初次分析

遍历整个链表,同时记录每个节点是否被访问过,如果被访问过,则返回true。遍历结束如果没有发现被访问过的节点,则返回false。

这时候我们需要一个Hash表来存储每个节点访问的情况。我们能不能不额外的引入这个哈希呢?

继续分析

一般这种都是用双指针,那么我们这个题能不能用双指针?

我们用一个指针标记头指针的位置。如果是个环,那么另一个指针会回到头指针。但是答案却不是,因为

img

只有这种情况是可以的,但是

img

却不行,起初看题目有个pos,则认为头指针就是环形的起始节点,那么我标记头指针就能判断答案,后来仔细看了下题目,才知道pos是leecode用来标记答案的,跟我们没有关系,题目说明了评测系统内部使用

这个题没想出解法,看了答案,使用了龟兔赛跑的思想。一个指针一个节点一个节点移动,另一个指针领先一步,两个节点两个节点的移动。

  • 如果没有环,当快兔走到终点时,则认为没有环,false。
  • 如果有环,那么跑到前边的兔子会从后边追上跑的慢的乌龟,true。

答案

public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

复杂度

  • 时间复杂度: O(n)。

    • 没有环时,快兔遍历1/2遍链表,结束。
    • 有环时,最坏的情况也就是遍历次数的情况就是头节点就是环的一部分或者进入环时快指针是慢指针的next节点。此时两个指针几乎相差整个环的长度,每次遍历两个指针的距离减一。此时是遍历次数最多的情况也就是环的长度。

    所以时间复杂度时O(n)。

  • 空间复杂度: O(1),只需要两个快慢指针。

总结

上边的时间复杂度可能不好理解。画个图理解下吧。

情况一

  • 初始时

image.png

  • 一次循环之后

image.png

  • 两次循环

image.png

  • 三次循环,这时候黑色和红色重合,则认为是个环。

image.png

这是最好的情况

情况二

  • 初始位置 距离黑色三个位置

image.png

  • 一次循环 距离黑色两个位置

image.png

  • 二次循环、距离黑色一个位置

image.png

  • 三次循环 重合

image.png

这是最坏情况。

情况三

  • 初始位置、距离黑色三个节点。

image.png

  • 一次循环、距离黑色两个节点

image.png

  • 二次循环、距离黑色一个节点

image.png

  • 三次循环、结束

    image.png

总结

时间复杂度取决于进入环时的两个快慢指针的位置。最好的情形就是情况一,遍历环前边的次数即可停止。最坏的情形就是情况二。可以看到黑色的球走过了所有的节点也就是O(n),所以最坏的时间复杂度是O(n)。

都来了,点个赞再走呗!

关注WangScaler,祝你升职、加薪、不提桶!

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
怒刷力扣(杨辉三角)
杨辉三角是在数学二项式中会遇到,在简单的算法题中出现的频率也是很高,不过确实是个简单的算法题,快来看看吧。
20 0
怒刷力扣(二叉树的中序遍历)
二叉树的中序遍历,前两种算法相对来说,比较容易理解,但是第三种,就需要自己思考思考了,想明白了其实也并不是很难。
14 0
怒刷力扣(合并两个有序数组)
一说到排序,往往大家习惯性的从头到尾进行处理,这种固化思维往往会影响我们对问题的处理。所以要多思考,换个方向进行思考,或许解决问题的方法更简单,所以生活中换位思考,也是一种难能可贵的品格。
19 0
怒刷力扣(爬楼梯)
斐波那契数列还会吗?初高中的求通项公式还会求吗?数学是不是白上了?如果你都还给老师了,那么赶紧找老师学回来吧。
16 0
怒刷力扣(最后一个单词的长度)
查找最后一个单词长度的大小,这个题的关键点就是处理最后几个字符是空字符串的情况,但是也不是很难,最简单的一道题了吧。
14 0
怒刷力扣(移除元素)
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
21 0
怒刷力扣(有效的括号)
这个题上大学的时候,就做过无数次,和水仙花数等等一样,印象深刻。关键点就是看出是栈,那么这个问题就很简单了。
18 0
+关注
wangscaler
Do you love , Love you do!
60
文章
1
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载