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

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

推荐阅读

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

一、题目

1、算法题目

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

题目链接:

来源:力扣(LeetCode)

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

2、题目描述

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

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

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

image.png

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

二、解题

1、思路分析

这道题可以遍历所有节点,然后遍历到一个节点后,判断该节点是否被访问过。

记录节点是否被访问过,可以使用哈希表,每次到达一个节点,如果节点存在于哈希表,则说明该链表是环形链表。

否则,就将该节点加入到哈希表中,重复这一过程,直到遍历完整个链表。

2、代码实现

代码参考:

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

image.png

3、时间复杂度

时间复杂度:O(N)

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

空间复杂度:O(N)

其中N是链表中的节点数,空间的开销主要是哈希表的开销,最坏的情况下需要将每个节点都插入到哈希表一次。

三、总结

这道题还可以使用双指针,用快慢指针,快指针每次走两步,慢指针每次走一步。
当快指针追上慢指针则表示有环。

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

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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