面试算法22:链表中环的入口节点(1)
题目
如果一个链表中包含环,那么应该如何找出环的入口节点?从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。
例如,在如图4.3所示的链表中,环的入口节点是节点3。

分析
第1步:确认是否包含环
定义两个指针并同时从链表的头节点出发,一个指针一次走一步,另一个指针一次走两步。如果链表中不包含环,走得快的指针直到抵达链表的尾节点都不会和走得慢的指针相遇。如果链表中包含环,走得快的指针在环里绕了一圈之后将会追上走得慢的指针。因此,可以根据一快一慢两个指针是否能够相遇来判断链表中是否包含环。
第2步:如何找到环的入口节点
定义两个指针来解决。先定义两个指针P1和P2,指向链表的头节点。如果链表中的环有n个节点,第1个指针P1先在链表中向前移动n步,然后两个指针以相同的速度向前移动。当第2个指针P2指向环的入口节点时,指针P1已经围绕环走了一圈又回到了入口节点。

第3步:如何得到环中节点的数目
前面在判断链表中是否有环时用到了一快一慢两个指针。如果两个指针相遇,则表明链表中存在环。两个指针之所以会相遇是因为快的指针绕环一圈追上慢的指针,因此它们相遇的节点一定是在环中。可以从这个相遇的节点出发一边继续向前移动一边计数,当再次回到这个节点时就可以得到环中节点的数目。
解
public class Test {public static void main(String[] args) {ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;listNode5.next = listNode6;listNode6.next = listNode3;ListNode result = detectCycle(listNode1);System.out.println(result.val);}public static ListNode detectCycle(ListNode head) {ListNode inLoop = getNodeInLoop(head);if (inLoop == null) {return null;}int loopCount = 1;for (ListNode n = inLoop; n.next != inLoop; n = n.next) {loopCount++;}ListNode fast = head;for (int i = 0; i < loopCount; i++) {fast = fast.next;}ListNode slow = head;while (slow != fast) {fast = fast.next;slow = slow.next;}return slow;}// 快慢指针找到相遇的节点private static ListNode getNodeInLoop(ListNode head) {if (head == null || head.next == null) {return null;}ListNode slow = head.next;ListNode fast = slow.next;while (slow != null && fast != null) {if (slow == fast)return slow;slow = slow.next;fast = fast.next;if (fast != null)fast = fast.next;}return null;}
}
相关文章:
面试算法22:链表中环的入口节点(1)
题目 如果一个链表中包含环,那么应该如何找出环的入口节点?从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。 例如,在如图4.3所示的链表中,环的入口节点是节点3。 分析 第1步:确认是否包含环…...
蓝桥杯---第二讲---二分与前缀和
文章目录 前言Ⅰ. 数的范围0x00 算法思路0x00 代码书写 Ⅱ. 数的三次方根0x00 算法思路0x01代码书写 Ⅲ. 前缀和0x00 算法思路0x01 代码书写 Ⅳ. 子矩阵的和0x00 算法思路0x01 代码书写 Ⅴ. 机器人跳跃问题0x00 算法思路0x01 代码书写 Ⅵ. 四平方和0x00 算法思路0x01 代码书写 …...
d3dx9_39.dll如何修复?最新修复d3dx9_39.dll方法分享
大家好!今天我要和大家分享的主题是“d3dx9_39.dll丢失的修复方法”。我们都知道,在使用电脑的过程中,经常会遇到各种问题,而其中最常见的就是文件丢失。d3dx9_39.dll就是其中一个常见的丢失文件。那么,如何修复这个丢…...
阿里云轻量应用服务器月流量限制说明(部分套餐不限流量)
阿里云轻量应用服务器部分套餐限制月流量,轻量应用服务器按照套餐售卖,有的套餐限制月流量,有的不限制流量。像阿里云轻量2核2G3M带宽轻量服务器一年108元和轻量2核4G4M带宽一年297.98元12个月,这两款是不限制月流量的。阿里云百科…...
项目设计:YOLOv5目标检测+机构光相机(intel d455和d435i)测距
1.介绍 1.1 Intel D455 Intel D455 是一款基于结构光(Structured Light)技术的深度相机。 与ToF相机不同,结构光相机使用另一种方法来获取物体的深度信息。它通过投射可视光谱中的红外结构光图案,然后从被拍摄物体表面反射回来…...
WPF中DataContext的绑定技巧
先看效果: 上面的绑定值都是我们自定义的属性,有了以上的提示,那么我们可以轻松绑定字段,再也不用担心错误了。附带源码。 目录 1.建立mvvm项目 2.cs后台使用DataContext绑定 3.xaml前台使用DataContext绑定 4.xaml前台使用Da…...
【Spring MVC研究】MVC原理:DispatcherServlet的初始化,初始化好等于MVC准备好
文章目录 1. EnableWebMVC 开启 MVC 功能2. 初始化自定义的 MVC 组件2.1. 初始化过程2.2. 如何分析复杂的 Spring 组件注册 3. 容器启动后会初始化 DispatcherServlet4. DispatcherServlet 初始化过程总结5. 资料参考 把DispatcherServlet 准备好意味着服务器已经可以处理请求了…...
Kafka的分布式架构与高可用性
导语 一开始我们就说过Kafka是一款开源的高吞吐、分布式的消息队列系统,那么今天我们就来说下它的分布式架构和高可用性以及双/多中心部署。 Kafka 体系架构简介 以下是 Kafka 的软件架构,整个 Kafka 体系结构由 Producer、Consumer、Broker、ZooKeepe…...
Spring Cloud学习笔记【分布式请求链路跟踪-Sleuth】
文章目录 Spring Cloud Sleuth概述概述主要功能:Sleuth中的术语和相关概念官网 zipkin配置下载运行zipkin下载zipkin运行 demo配置服务提供者 lf-userpom.xmlapplication.ymlUserController 服务调用者 lf-authpom.xmlapplication.ymlAuthController 测试 Spring Cl…...
Java开发中的操作日志详解(InsCode AI 创作助手)
Java开发中的操作日志详解 一、操作日志的作用 故障排除和调试: 操作日志可以记录应用程序的各种活动,包括错误、异常、警告和信息性消息。这有助于开发人员快速定位和解决问题。性能分析: 通过记录关键操作和性能指标,操作日志…...
FutureTask和CompletableFuture的模拟使用
模拟了查询耗时操作,并使用FutureTask和CompletableFuture分别获取计算结果,统计执行时长 package org.alllearn.futurtask;import com.google.common.base.Stopwatch; import com.google.common.collect.Lists; import lombok.AllArgsConstructor; imp…...
Redis作为缓存,mysql的数据如何与redis进行同步?
Redis作为缓存,mysql的数据如何与redis进行同步? 一定要设置前提,先介绍业务背景 延时双删 双写一致性:当修改了数据库的数据也要同时更新缓存的数据,缓存和数据库的数据要保持一致 读操作:缓存命中,直接返回;缓存未…...
申请免费 SSL 证书为您的小程序加密通信
在今天的网络环境中,数据安全和隐私保护变得尤为重要。无论是网站还是应用程序,为其提供安全的通信渠道都是至关重要的。对于小程序开发者来说,使用 SSL(Secure Sockets Layer)证书可以有效地保障用户数据的安全&#…...
Go 并发编程
并发编程 1.1 并发与并⾏ 并⾏与并发是两个不同的概念,普通解释: 并发:交替做不同事情的能⼒并⾏:同时做不同事情的能⼒ 如果站在程序员的⻆度去解释是这样的: 并发:不同的代码块交替执⾏并⾏…...
鱼眼相机去畸变(图像拉直/展开/矫正)算法及实战总结
本文介绍两种方法 1、经纬度矫正法 2、棋盘格矫正法 一、经纬度矫正法 1、算法说明 经纬度矫正法, 可以把鱼眼图想象成半个地球, 然后将地球展开成地图,经纬度矫正法主要是利用几何原理, 对图像进行展开矫正。 经过P点的入射光线…...
es6 数据类型
es6 数据类型 map 数据类型 >Map 对象保存键值对。 用途 : Object的key无法支持该数据时需要了解对象大小时 map 数据类型任何值(对象或者原始值) 都可以作为一个键。 Object 的键只能是字符串 let myMap new Map(); let myMap1 new Map(); var keyStrin…...
【postgresql】
看到group by 1,2 和 order by 1, 2。看不懂,google,搜到了Stack Overflow 上有回答 What does SQL clause “GROUP BY 1” mean? 大概意思就是,group by, order by 后面跟数字,指的是 selec…...
【C++】空间配置器 allocator:原理及底层解析
文章目录 空间配置器一级空间配置器二级空间配置器1. 内存池2. SGI-STL中二级空间配置器设计 - - 哈希桶3. 二级空间配置器的空间申请 空间配置器的默认选择空间配置器的在封装:添加了数据类型大小空间配置器对象的构造与析构 容器中的 allocator 空间配置器 提到空…...
微信小程序 movable-area 区域拖动动态组件演示
movable-area 组件在小程序中的作用是用于创建一个可移动的区域,可以在该区域内拖动视图或内容。这个组件常用于实现可拖动的容器或可滑动的列表等交互效果。 使用 movable-area 组件可以对其内部的 movable-view 组件进行拖动操作,可以通过设置不同的属…...
隔离上网,安全上网
SDC沙盒数据防泄密系统(安全上网,隔离上网) •深信达SDC沙盒数据防泄密系统,是专门针对敏感数据进行防泄密保护的系统,根据隔离上网和安全上网的原则实现数据的代码级保护,不会影响工作效率,不…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...
