【LeetCode】环形链表 II [M](链表)
142. 环形链表 II - 力扣(LeetCode)
一、题目
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:

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

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

输入:head = [1], pos = -1 输出:返回 null 解释:链表中没有环。
提示:
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
二、代码
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {// 过滤空链表、单节点链表和双节点链表,这三种情况一定是无环链表,直接返回nullif (head == null || head.next == null || head.next.next == null) {return null;}// 设置两个快慢指针,快指针一次走两步,满指针一次走一步// 提前将快慢指针的初始位置设置好,这一步很重要,不能将初始位置都设置成head,会导致结果错误ListNode slow = head.next; // n1 -> slowListNode fast = head.next.next; // n2 -> fastwhile (fast != slow) {// 如果快指针在遍历过程中出现了结尾为空的情况,直接返回null,表示一定没有环if (fast.next == null || fast.next.next == null) {return null;}// 快指针一次走两步fast = fast.next.next;// 慢指针一次走一步slow = slow.next;}// 执行到这里说明快慢指针重合了,此时将快指针重新回到头节点fast = head;// 快慢指针都用相同的步长向后遍历,当再次相遇的时候,相遇节点就是第一个入换节点while (fast != slow) {fast = fast.next;slow = slow.next;}// 返回入环节点return fast;}
}
三、解题思路
用快慢指针解决这个问题,就是设置两个快慢指针从头开始向后遍历链表(快指针一次走两步,慢指针一次走1步),如果快指针遍历到了null,就说明该节点没有环,因为有环节点不可能有节点next指向null。如果快指针和慢指针再次相会,就说明快指针已经沿着链表转了一圈又转回来了,再次追上了慢指针,比慢指针多跑了一圈。这个时候慢指针保持在相遇位置,快指针再次回到链表头节点,两个指针再次以相同的步长向后遍历(全都一次只走一步),这样当两个节点再次相遇的时候,相遇节点就是该链表的入环节点(这个过程中,慢指针就是一直在环中转圈,快指针当走到入环节点的时候,慢指针也会转圈转到入环节点)。
相关文章:
【LeetCode】环形链表 II [M](链表)
142. 环形链表 II - 力扣(LeetCode) 一、题目 给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链…...
Unity之如何实现一个VR任务(剧情)系统
一.前言 最近再做一个VR项目,里面有大量的剧情和VR操作任务。 比如: 1.张三说了什么话,干了什么事,然后,李四又说了什么,做了什么动画,完了之后,场景中某个物体高亮,让我们触摸或者射线点击(pc的话鼠标点击)和其发生交互。 2.我们使用VR手柄或者鼠标与场景中的一个…...
k8s核心概念与kubectl命令行工具的使用
k8s官方文档Kubernetes 文档 | Kubernetes作用:kubernetes用于容器化应用程序的部署,扩展和管理。目标:是让部署容器化应用简单高效。Kubernetes集群架构与组件 Master组件 kube-apiserverkubernetes API,集群的统一入口ÿ…...
【零基础入门前端系列】—无序列表、有序列表、定义列表(四)
一、HTML无序列表 无序列表是一个项目的列表,此列项目使用粗体圆点(典型的小黑圆圈)进行标记。 无序列表使用 <ul> 标签 <ul> <li>Coffee</li> <li>Milk</li> </ul>嵌套结构: <…...
为什么重写equals还要重写hashcode方法
目录equals方法hashCode方法为什么要一起重写?总结面试如何回答重写 equals 时为什么一定要重写 hashCode?要想了解这个问题的根本原因,我们还得先从这两个方法开始说起。 以下是关于hashcode的一些规定: 两个对象相等࿰…...
电子技术——电流镜负载的差分放大器
电子技术——电流镜负载的差分放大器 目前我们学习的差分放大器都是使用的是差分输出的方式,即在两个漏极之间获取电压。差分输出主要有以下优势: 降低了共模信号的增益,提高了共模抑制比。降低了输入偏移电压。提升了差分输入的增益。 由于…...
go面试题
1.json包在使用的时候,结构体里的变量不加tag能不能正常转成json里的字段? 如果变量首字母小写,则为private。无论如何不能转,因为取不到反射信息。如果变量首字母大写,则为public。 不加tag,可以正常转为j…...
攻防世界-Confusion1
题目 访问题目场景 某天,Bob说:PHP是最好的语言,但是Alice不赞同。所以Alice编写了这个网站证明。在她还没有写完的时候,我发现其存在问题。(请不要使用扫描器) 然后结合图片我们知道,这个网址是python写的࿰…...
机器学习实战--梯度下降法进行波士顿房价预测
前言: Hello大家好,我是Dream。 今天来学习一下如何使用机器学习梯度下降法进行波士顿房价预测,这是简单的一个demo,主要展示的是一些小小的思路~ 本文目录:一、波士顿房价预测1.全部的数据可视化2.地理数据可视化3.房…...
黑马】后台管理-项目优化和上线
一。项目优化优化1,加载进度条显示安装一个运行依赖,nprogress然后导包,调用对象展示和隐藏在main中基于拦截器实现展示进度条和隐藏进度条的效果如果触发请求拦截器,证明发起请求,希望展示进度条,如果触发…...
Web 框架 Flask 快速入门(三)数据库-MySQL
课程地址:Python Web 框架 Flask 快速入门 文章目录数据库1、数据库的安装与配置2、数据库的简单使用——增删改1. 定义数据模型2. 增删改3、 关系引用——表的关联4、查询——通过SQLAlchemy扩展5、其他1. 数据模型的实现(疑惑)6、Bug记录1.…...
牛客网Python篇数据分析习题(六)
1.某公司计划举办一场运动会,现有运动会项目数据集items.csv。 包含以下字段: item_id:项目编号; item_name:项目名称; location:比赛场地。 有员工报名情况数据集signup.csv。包含以下字段: employee_id&a…...
Ansible的安装及部署
目录 一、Ansible对于企业运维的重大意义 二、Ansible的安装 三、构建Ansible清单 1.直接书写受管主机名或ip,每行一个 2.设定受管主机的组[组名称] 四、Ansible配置文件参数详解 1、配置文件的分类与优先级 2.配置新用户的Ansible配置 3.生成免密认证 本章…...
链表题目总结 -- 递归
目录一. 递归反转整个链表1. 思路简述2. 代码3. 总结二. 反转链表前 N 个节点1. 思路简述2. 代码3. 总结三、反转链表的一部分1. 思路简述2. 代码3.总结四、从节点M开始反转后面的链表1. 思路简述2. 代码3.总结一. 递归反转整个链表 题目链接:https://leetcode.cn/…...
重写-linux内存管理-伙伴分配器(一)
文章目录一、伙伴系统的结构二、初始化三、分配内存3.1 prepare_alloc_pages3.2 get_page_from_freelist3.2.1 zone_watermark_fast3.2.2 zone_watermark_ok3.2.3 rmqueue3.2.3.1 rmqueue_pcplist3.2.3.2 __rmqueue3.2.3.2.1 __rmqueue_smallest3.2.3.2.2 __rmqueue_fallback3.…...
为什么要用springboot进行开发呢?
文章目录前言1、那么Springboot是怎么实现自动配置的1.1 启动类1.2 SpringBootApplication1.3 Configuration1.4 ComponentScan1.5 EnableAutoConfiguration1.6 两个重要注解1.7 AutoConfigurationPackage注解1.8 Import(AutoConfigurationImportSelector.class)注解1.9自动配置…...
设备树信息解析相关函数
一。可以通过三种不同的方式解析设备树节点: 1.根据设备树节点的名字解析设备树节点 struct device_node *of_find_node_by_name(struct device_node *from, const char *name); 参数: from:当前节点父节点首地址 name:设备树节点名字 …...
LeetCode-1124. 表现良好的最长时间段【哈希表,前缀和,单调栈】
LeetCode-1124. 表现良好的最长时间段【哈希表,前缀和,单调栈】题目描述:解题思路一:查字典。cur是当前的前缀和(劳累与不劳累天数之差),向前遍历。有两种情况。情况一,若cur大于0则是[0,i]的劳累与不劳累天…...
vue-router路由配置
介绍:路由配置主要是用来确定网站访问路径对应哪个文件代码显示的,这里主要描述路由的配置、子路由、动态路由(运行中添加删除路由) 1、npm添加 npm install vue-router // 执行完后会自动在package.json中添加 "vue-router…...
中国计算机设计大赛来啦!用飞桨驱动智慧救援机器狗
中国大学生计算机设计大赛是我国高校面向本科生最早的赛事之一,自2008年开赛至今,一直由教育部高校与计算机相关教指委等或独立或联合主办。大赛的目的是以赛促学、以赛促教、以赛促创,为国家培养德智体美劳全面发展的创新型、复合型、应…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
Xela矩阵三轴触觉传感器的工作原理解析与应用场景
Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知,帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量,能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度,还为机器人、医疗设备和制造业的智…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
