怒刷力扣(环形链表)

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

环形链表

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,祝你升职、加薪、不提桶!

目录
相关文章
|
1月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
35 1
|
1月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
50 0
Leetcode第21题(合并两个有序链表)
|
1月前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
18 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
44 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
1月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
78 0
|
1月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
21 0
|
1月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
17 0
|
1月前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
12 0
|
1月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
30 0