[Java·算法·简单] LeetCode 141. 环形链表 详细解读

简介: [Java·算法·简单] LeetCode 141. 环形链表 详细解读

题目

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


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


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


示例

示例1

输入:head = [3,2,0,-4], pos = 1

输出:true

解释:链表中有一个环,其尾部连接到第二个节点。


8af83736ff0f74b0b6d1b1997fa1ee5e_7035a5b8c6668aaa3ef536f880df6cf6.png

输入:head = [1,2], pos = 0

输出:true

解释:链表中有一个环,其尾部连接到第一个节点。


示例3

输入:head = [1], pos = -1

输出:false

解释:链表中没有环。


提示

👉️ 力扣原文

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
 
public class Solution {
    public 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; // 快指针追上慢指针,说明链表中存在环
    }
}


详细解读

这个方法使用了双指针技术来检测链表中是否存在环。下面是对方法的详细解读:


  1. 初始条件检查
  • 方法开始时,首先检查链表是否为空,或者是否只有一个节点。如果链表为空或者只有一个节点,肯定不存在环,因此直接返回 false
  1. 初始化指针
  • 创建两个指针 slowfast,初始时分别指向链表的头节点 headhead.next
  • 这里快指针 fast 比慢指针 slow 快一步是为了保证在检测环时不会因为快指针提前到达末尾而遗漏环的检测。

3.循环检测

  • 使用一个 while 循环,条件是 slow 指针不等于 fast 指针。
  • 在循环中,先检查快指针 fast 是否为 null,如果是,说明已经到达了链表的末尾,即链表中不存在环,直接返回 false。
  • 然后让慢指针 slow 前进一步,即 slow = slow.next。
  • 接着让快指针 fast 前进两步,即 fast = fast.next.next。
  • 循环结束的条件是 slow 和 fast 相遇,即两个指针指向了同一个节点,表示链表中存在环。


4.返回结果

  • 如果循环结束时,slowfast 相遇了,说明链表中存在环,返回 true
  • 如果循环结束时,快指针 fast 到达了链表的末尾,则说明链表中不存在环,返回 false


这种方法的时间复杂度是 O(n),其中 n 是链表的节点数,因为在最坏情况下,快指针 fast 最多会遍历整个链表一次。而空间复杂度是 O(1),因为只使用了常数个额外的指针。

相关文章
|
12月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
125 1
|
6月前
|
算法 Go
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
190 10
|
6月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
105 0
|
12月前
|
算法 索引
❤️算法笔记❤️-(每日一刷-141、环形链表)
❤️算法笔记❤️-(每日一刷-141、环形链表)
123 0
|
7月前
|
存储 监控 算法
员工电脑监控系统中的 C# 链表算法剖析-如何监控员工的电脑
当代企业管理体系中,员工电脑监控已成为一个具有重要研究价值与实践意义的关键议题。随着数字化办公模式的广泛普及,企业亟需确保员工对公司资源的合理利用,维护网络安全环境,并提升整体工作效率。有效的电脑监控手段对于企业实现这些目标具有不可忽视的作用,而这一过程离不开精妙的数据结构与算法作为技术支撑。本文旨在深入探究链表(Linked List)这一经典数据结构在员工电脑监控场景中的具体应用,并通过 C# 编程语言给出详尽的代码实现与解析。
105 5
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
200 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
313 25
|
8月前
|
存储 监控 算法
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
114 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
11月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
216 4
|
11月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!

热门文章

最新文章