☆打卡算法☆LeetCode 142. 环形链表 II 算法解析

恬静的小魔龙 发表于 2022/06/29 11:26:07 2022/06/29
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个链表的头节点,判断链表中是否有环。”题目链接:来源:力扣(LeetCode)链接: 142. 环形链表 II - 力扣(...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个链表的头节点,判断链表中是否有环。”

题目链接:

来源:力扣(LeetCode)

链接: 142. 环形链表 II - 力扣(LeetCode)

2、题目描述

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

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

不允许修改 链表。

image.png

示例 1:
输入: head = [3,2,0,-4], pos = 1
输出: 返回索引为 1 的链表节点
解释: 链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入: head = [1,2], pos = 0
输出: 返回索引为 0 的链表节点
解释: 链表中有一个环,其尾部连接到第一个节点。

二、解题

1、思路分析

这道题跟141题环形链表类似,解法也类似,也是可以使用哈希表来解题。

遍历所有节点,每到达一个节点,就判断该节点是否存在于哈希表中,存在说明是环形链表,不存在就将该节点加入到哈希表中,直到遍历结束。

在上一篇文章中我提到可以使用双指针,那么这道题就用双指针来解吧。

使用双指针,用快慢指针,快指针每次走两步,慢指针每次走一步。

当快指针追上慢指针则表示有环。

如果快指针指向null,这说明链表没环。

2、代码实现

代码参考:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

image.png

3、时间复杂度

时间复杂度:O(N)

其中N是链表中的节点数。

空间复杂度:O(1)

只是用了几个指针变量。

三、总结

总结一下为何慢指针第一圈走不完一定会和快指针相遇:

第一步,快指针先进入环

第二步:当慢指针刚到达环的入口时,快指针此时在环中的某个位置(也可能此时相遇)

第三步:设此时快指针和慢指针距离为x,若在第二步相遇,则x = 0;

第四步:设环的周长为n,那么看成快指针追赶慢指针,需要追赶n-x;

第五步:快指针每次都追赶慢指针1个单位,设慢指针速度1/s,快指针2/s,那么追赶需要(n-x)s

第六步:在n-x秒内,慢指针走了n-x单位,因为x>=0,则慢指针走的路程小于等于n,即走不完一圈就和快指针相遇

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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