前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >☆打卡算法☆LeetCode 141. 环形链表 算法解析

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

作者头像
恬静的小魔龙
发布2022-08-07 10:36:43
2260
发布2022-08-07 10:36:43
举报
文章被收录于专栏:Unity3DUnity3D
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

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

题目链接:

来源:力扣(LeetCode)

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

2、题目描述

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

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

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

image.png
image.png
代码语言:javascript
复制
示例 1:
输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表中有一个环,其尾部连接到第二个节点。
代码语言:javascript
复制
示例 2:
输入: head = [1,2], pos = 0
输出: true
解释: 链表中有一个环,其尾部连接到第一个节点。

二、解题

1、思路分析

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

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

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

2、代码实现

代码参考:

代码语言:javascript
复制
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
image.png

3、时间复杂度

时间复杂度:O(N)

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

空间复杂度:O(N)

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

三、总结

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

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-06-01,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目
    • 1、算法题目
      • 2、题目描述
      • 二、解题
        • 1、思路分析
          • 2、代码实现
            • 3、时间复杂度
            • 三、总结
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档