当前位置: 首页 > news >正文

面试算法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)

题目 如果一个链表中包含环&#xff0c;那么应该如何找出环的入口节点&#xff1f;从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点。 例如&#xff0c;在如图4.3所示的链表中&#xff0c;环的入口节点是节点3。 分析 第1步&#xff1a;确认是否包含环…...

蓝桥杯---第二讲---二分与前缀和

文章目录 前言Ⅰ. 数的范围0x00 算法思路0x00 代码书写 Ⅱ. 数的三次方根0x00 算法思路0x01代码书写 Ⅲ. 前缀和0x00 算法思路0x01 代码书写 Ⅳ. 子矩阵的和0x00 算法思路0x01 代码书写 Ⅴ. 机器人跳跃问题0x00 算法思路0x01 代码书写 Ⅵ. 四平方和0x00 算法思路0x01 代码书写 …...

d3dx9_39.dll如何修复?最新修复d3dx9_39.dll方法分享

大家好&#xff01;今天我要和大家分享的主题是“d3dx9_39.dll丢失的修复方法”。我们都知道&#xff0c;在使用电脑的过程中&#xff0c;经常会遇到各种问题&#xff0c;而其中最常见的就是文件丢失。d3dx9_39.dll就是其中一个常见的丢失文件。那么&#xff0c;如何修复这个丢…...

阿里云轻量应用服务器月流量限制说明(部分套餐不限流量)

阿里云轻量应用服务器部分套餐限制月流量&#xff0c;轻量应用服务器按照套餐售卖&#xff0c;有的套餐限制月流量&#xff0c;有的不限制流量。像阿里云轻量2核2G3M带宽轻量服务器一年108元和轻量2核4G4M带宽一年297.98元12个月&#xff0c;这两款是不限制月流量的。阿里云百科…...

项目设计:YOLOv5目标检测+机构光相机(intel d455和d435i)测距

1.介绍 1.1 Intel D455 Intel D455 是一款基于结构光&#xff08;Structured Light&#xff09;技术的深度相机。 与ToF相机不同&#xff0c;结构光相机使用另一种方法来获取物体的深度信息。它通过投射可视光谱中的红外结构光图案&#xff0c;然后从被拍摄物体表面反射回来…...

WPF中DataContext的绑定技巧

先看效果&#xff1a; 上面的绑定值都是我们自定义的属性&#xff0c;有了以上的提示&#xff0c;那么我们可以轻松绑定字段&#xff0c;再也不用担心错误了。附带源码。 目录 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是一款开源的高吞吐、分布式的消息队列系统&#xff0c;那么今天我们就来说下它的分布式架构和高可用性以及双/多中心部署。 Kafka 体系架构简介 以下是 Kafka 的软件架构&#xff0c;整个 Kafka 体系结构由 Producer、Consumer、Broker、ZooKeepe…...

Spring Cloud学习笔记【分布式请求链路跟踪-Sleuth】

文章目录 Spring Cloud Sleuth概述概述主要功能&#xff1a;Sleuth中的术语和相关概念官网 zipkin配置下载运行zipkin下载zipkin运行 demo配置服务提供者 lf-userpom.xmlapplication.ymlUserController 服务调用者 lf-authpom.xmlapplication.ymlAuthController 测试 Spring Cl…...

Java开发中的操作日志详解(InsCode AI 创作助手)

Java开发中的操作日志详解 一、操作日志的作用 故障排除和调试&#xff1a; 操作日志可以记录应用程序的各种活动&#xff0c;包括错误、异常、警告和信息性消息。这有助于开发人员快速定位和解决问题。性能分析&#xff1a; 通过记录关键操作和性能指标&#xff0c;操作日志…...

FutureTask和CompletableFuture的模拟使用

模拟了查询耗时操作&#xff0c;并使用FutureTask和CompletableFuture分别获取计算结果&#xff0c;统计执行时长 package org.alllearn.futurtask;import com.google.common.base.Stopwatch; import com.google.common.collect.Lists; import lombok.AllArgsConstructor; imp…...

Redis作为缓存,mysql的数据如何与redis进行同步?

Redis作为缓存&#xff0c;mysql的数据如何与redis进行同步&#xff1f; 一定要设置前提&#xff0c;先介绍业务背景 延时双删 双写一致性:当修改了数据库的数据也要同时更新缓存的数据&#xff0c;缓存和数据库的数据要保持一致 读操作:缓存命中&#xff0c;直接返回;缓存未…...

申请免费 SSL 证书为您的小程序加密通信

在今天的网络环境中&#xff0c;数据安全和隐私保护变得尤为重要。无论是网站还是应用程序&#xff0c;为其提供安全的通信渠道都是至关重要的。对于小程序开发者来说&#xff0c;使用 SSL&#xff08;Secure Sockets Layer&#xff09;证书可以有效地保障用户数据的安全&#…...

Go 并发编程

并发编程 1.1 并发与并⾏ 并⾏与并发是两个不同的概念&#xff0c;普通解释&#xff1a; 并发&#xff1a;交替做不同事情的能⼒并⾏&#xff1a;同时做不同事情的能⼒ 如果站在程序员的⻆度去解释是这样的&#xff1a; 并发&#xff1a;不同的代码块交替执⾏并⾏&#xf…...

鱼眼相机去畸变(图像拉直/展开/矫正)算法及实战总结

本文介绍两种方法 1、经纬度矫正法 2、棋盘格矫正法 一、经纬度矫正法 1、算法说明 经纬度矫正法&#xff0c; 可以把鱼眼图想象成半个地球&#xff0c; 然后将地球展开成地图&#xff0c;经纬度矫正法主要是利用几何原理&#xff0c; 对图像进行展开矫正。 经过P点的入射光线…...

es6 数据类型

​ es6 数据类型 map 数据类型 >Map 对象保存键值对。 用途 &#xff1a; Object的key无法支持该数据时需要了解对象大小时 map 数据类型任何值(对象或者原始值) 都可以作为一个键。 Object 的键只能是字符串 let myMap new Map(); let myMap1 new Map(); var keyStrin…...

【postgresql】

看到group by 1&#xff0c;2 和 order by 1&#xff0c; 2。看不懂&#xff0c;google&#xff0c;搜到了Stack Overflow 上有回答 What does SQL clause “GROUP BY 1” mean? 大概意思就是&#xff0c;group by&#xff0c; order by 后面跟数字&#xff0c;指的是 selec…...

【C++】空间配置器 allocator:原理及底层解析

文章目录 空间配置器一级空间配置器二级空间配置器1. 内存池2. SGI-STL中二级空间配置器设计 - - 哈希桶3. 二级空间配置器的空间申请 空间配置器的默认选择空间配置器的在封装&#xff1a;添加了数据类型大小空间配置器对象的构造与析构 容器中的 allocator 空间配置器 提到空…...

微信小程序 movable-area 区域拖动动态组件演示

movable-area 组件在小程序中的作用是用于创建一个可移动的区域&#xff0c;可以在该区域内拖动视图或内容。这个组件常用于实现可拖动的容器或可滑动的列表等交互效果。 使用 movable-area 组件可以对其内部的 movable-view 组件进行拖动操作&#xff0c;可以通过设置不同的属…...

隔离上网,安全上网

SDC沙盒数据防泄密系统&#xff08;安全上网&#xff0c;隔离上网&#xff09; •深信达SDC沙盒数据防泄密系统&#xff0c;是专门针对敏感数据进行防泄密保护的系统&#xff0c;根据隔离上网和安全上网的原则实现数据的代码级保护&#xff0c;不会影响工作效率&#xff0c;不…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...