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

【LeetCode 算法】Linked List Cycle II 环形链表 II

文章目录

Linked List Cycle II 环形链表 II

问题描述:

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

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

不允许修改 链表。

链表中节点的数目范围是 [ 0 , 1 0 4 ] − 1 0 5 < = N o d e . v a l < = 1 0 5 p o s 为 − 1 或者链表中的一个有效索引 链表中节点的数目范围是 [0, 10^4]\\ -10^5 <= Node.val <= 10^5\\ pos 为 -1 或者链表中的一个 有效索引 链表中节点的数目范围是[0,104]105<=Node.val<=105pos1或者链表中的一个有效索引

分析

和昨天的环形链表类似,利用哈希可以在 O ( N ) O(N) O(N)的时间下,找到第一个节点。

另一种就是空间为常数快慢指针,就是昨天发的那个,它还有个比较学术的名字,Floyd判圈算法(Floyd Cycle Detection Algorithm),它的应用场景很广泛,可以自行Bing,Google。

它的思路比较简单,如果存在环,那么先找到快慢指针在环中的相遇的点 x,然后再让2个指针分别从head,x出发,直到2者相遇,就是环的入口点

思路很简单,但是大部分人还是不一定能AC。

为什么按照这个思路,可以找到的点一定是入口点?

讨论的前提是有环。

假设入口点是y,那么从 h e a d head head到达y需要 a步,从y到达2指针的相遇点x要走b步,b一定是小于n的,从x继续走c步到达入口y,所以环的大小 b + c b+c b+c
f a s t 走的路程 = a + ( k + 1 ) ( b + c ) + b fast 走的路程 = a+ (k+1)(b+c) + b fast走的路程=a+(k+1)(b+c)+b。 a 是无环段,b是环的入口到x的路程,而 ( k + 1 ) ( b + c ) (k+1)(b+c) (k+1)(b+c) 就是跑环的圈数 k > = 0 k>=0 k>=0
s l o w 的路程 = a + b slow的路程 = a+b slow的路程=a+b ,因为fast的速度是slow的2倍,所以路程也是其2倍,即
a + b + ( k + 1 ) ( b + c ) = 2 ∗ ( a + b ) ( k + 1 ) ( b + c ) = a + b k ( b + c ) + c = a a+b +(k+1)(b+c) = 2*(a+b)\\ (k+1)(b+c) = a+b\\ k(b+c)+c = a a+b+(k+1)(b+c)=2(a+b)(k+1)(b+c)=a+bk(b+c)+c=a

到这里就会可以得到一个结论,设置2个指针分别从点x和head出发,每次一步,如果相遇就是入口点

如果你无法理解这个结论.

提示你可以从路程的角度来思考,即一个从x出发的指针,它可能走c,或者是k(b+c)+c,然后恰好与另一个指针在入口相遇。

时间复杂度 O ( N ) 时间复杂度O(N) 时间复杂度O(N)

空间复杂度 O ( 1 ) 空间复杂度O(1) 空间复杂度O(1)

代码

哈希

public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet();ListNode p = head;while(p!=null){if(!set.add(p)) return p;p = p.next;}return null;} 

时间复杂度 O ( N ) O(N) O(N)

空间复杂度 O ( N ) O(N) O(N)

快慢指针

public ListNode detectCycle(ListNode head) {if(head==null||head.next==null) return null;        ListNode vh = new ListNode(-1);vh.next = head;ListNode f = vh, s = vh;while(f!=null&&f.next!=null){ f = f.next.next;s = s.next;if(f==s) break;} if(f==null||f.next==null) return null;ListNode p = vh, q = f;while(p!=q){p = p.next;q = q.next;}return q;}

时间复杂度 O ( N ) O(N) O(N)

空间复杂度 O ( 1 ) O(1) O(1)

Tag

LinkedList

Hash

Two Pointers

相关文章:

【LeetCode 算法】Linked List Cycle II 环形链表 II

文章目录 Linked List Cycle II 环形链表 II问题描述&#xff1a;分析代码哈希快慢指针 Tag Linked List Cycle II 环形链表 II 问题描述&#xff1a; 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链…...

蒸散发与植被总初级生产力估算

目标 熟悉蒸散发ET及其组分&#xff08;植被蒸腾Ec、土壤蒸发Es、冠层截留Ei&#xff09;、植被总初级生产力GPP的概念和碳水耦合的基本原理&#xff1b;掌握利用Python与ArcGIS工具进行课程相关的操作&#xff1b;熟练掌握国际上流行的Penman-Monteith模型&#xff0c;并能够…...

uniapp微信小程序底部弹窗自定义组件

基础弹窗效果组件 <template><view><viewclass"tui-actionsheet-class tui-actionsheet":class"[show ? tui-actionsheet-show : ]"><view class"regional-selection">底部弹窗</view></view><!-- 遮罩…...

人工智能的最新进展:2024年将会发生什么?

文章目录 2024年AI最新发展2024年AI具体应用2024年AI的具体预测 ✍创作者&#xff1a;全栈弄潮儿 &#x1f3e1; 个人主页&#xff1a; 全栈弄潮儿的个人主页 &#x1f3d9;️ 个人社区&#xff0c;欢迎你的加入&#xff1a;全栈弄潮儿的个人社区 &#x1f4d9; 专栏地址&#…...

使用Golang实现一套流程可配置,适用于广告、推荐系统的业务性框架——组合应用

在《使用Golang实现一套流程可配置&#xff0c;适用于广告、推荐系统的业务性框架——简单应用》中&#xff0c;我们看到了各种组合Handler的组件&#xff0c;如HandlerGroup和Layer。这些组件下面的子模块又是不同组件&#xff0c;比如LayerCenter的子组件是Layer。如果此时我…...

DNS入门学习:DNS缓存的原理和作用(中科三方)

在实际业务场景中&#xff0c;DNS解析过程并不总是严格遵循从根域名服务器、顶级域名服务器再到权威域名服务器的一级级查询过程&#xff0c;这只是一个标准状态。为了节省全球查询的时间&#xff0c;同时减轻各级服务器的解析压力&#xff0c;DNS系统中引入了缓存机制。本文中…...

Linux虚拟机安装tomcat(图文详解)

目录 第一章、xshell工具和xftp的使用1.1&#xff09;xshell下载与安装1.2&#xff09;xshell连接1.3&#xff09;xftp下载安装和连接 第二章、安装tomcat1.1&#xff09;关闭防火墙&#xff0c;传输tomcat压缩包到Linux虚拟机12&#xff09;启动tomcat 第一章、xshell工具和xf…...

Matlab对TMS320F28335编程--SVPWM配置互补PWM输出

前言 F28335中断 目的&#xff1a;FOC的核心算法及SVPWM输出&#xff0c;SVPWM的载波频率10kHz&#xff0c;SVPWM的每个周期都会触发ADC中断采集相电流&#xff0c;SVPWM为芯片ePWM4、5、6通道&#xff0c;配置死区 1、配置中断SVPWM进ADC中断&#xff0c;查上表知CPU1,PIE1 …...

MySQL数据库——多表操作

文章目录 前言多表关系一对一关系一对多/多对一关系多对多关系 外键约束创建外键约束插入数据删除带有外键约束的表的数据删除外键约束 多表联合查询数据准备交叉连接查询内连接查询外连接查询左外连接查询右外连接查询满外连接查询 子查询子查询关键字ALL 关键字ANY 和 SOME 关…...

Java版本spring cloud + spring boot企业电子招投标系统源代码 tbms

​ 功能模块&#xff1a; 待办消息&#xff0c;招标公告&#xff0c;中标公告&#xff0c;信息发布 描述&#xff1a; 全过程数字化采购管理&#xff0c;打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力&#xff0c;为…...

css实现,正常情况下div从左到右一次排列,宽度超出时,右侧最后一个div固定住,左侧其他div滚动

需求:正常情况下 宽度超出时: 实现: <templete><div class"jieduanbox"><div v-for"(item, index) in stageList" :key"index" style"display: inline-block">.......</div><div class"rightBtn&q…...

【Linux手动搭建Sftp,创建用户、用户组及删除用户】

SFTP &#xff08;Secure File Transfer Protocol&#xff09;是一种安全的文件传输协议&#xff0c;基于SSH协议进行加密传输。在进行文件传输时&#xff0c;SFTP客户端通过SSH协议与服务器进行连接&#xff0c;并且通过使用公钥和/或密码进行身份验证&#xff0c;从而确保传输…...

云上 Index:看「简墨」如何为云原生打造全新索引

拓数派首款数据计算引擎 PieCloudDB Database 是一款全新的云原生虚拟数仓。为了提升用户使用体验&#xff0c;提高查询效率&#xff0c;在实现存算分离的同时&#xff0c;PieCloudDB 设计与打造了全新的存储引擎「简墨」等模块&#xff0c;并针对云场景和分析型场景设计了高效…...

Linux安装cuda和cudnn教程

Linux安装cuda和cudnn教程 文章目录 1.下载cuda和cudnn2. 安装cuda并检验安装是否成功3. 安装cudnn4.验证cuda是否能用代码附件&#xff1a;解压各种格式文件的Linux命令参考文献 卸载之前的cuda 卸载之前的cuda教程 1.下载cuda和cudnn CUDA下载地址&#xff1a;https://dev…...

短视频矩阵源码

一、短视频矩阵源码搭建解析&#xff1a; 目录 一、短视频矩阵源码搭建解析&#xff1a; 二、短视频矩阵源码的开发路径分享&#xff1a; 三、短视频矩阵系统开发应具备哪些能力&#xff1f; 短视频技术开发能力&#xff1a; 开发人员应具备短视频相关技术能力&#xff0c…...

群狼调研—连锁化妆品品牌门店神秘顾客调查的行家

连锁化妆品品牌门店神秘顾客调查作为群狼调研(湖南专业市场调查)的优势业务之一&#xff0c;公司成立至今已承包包括北京、上海、广州、深圳、长沙在内全国多个城市上百家不同化妆品品牌客户的神秘顾客调查服务&#xff0c;在创新性、行业操守及客户服务等方面赢得了广大客户的…...

C# 回文链表

234 回文链表 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true 示例 2&#xff1a; 输入&…...

基于freertos的温湿度蓝牙系统

前言&#xff1a;本项目主要是基于freertos的小项目&#xff0c;目的是为了巩固近期学习的知识&#xff0c;功能较简单&#xff0c;可自行扩充。 一、项目基本架构 项目基本功能&#xff1a;通过STM32单片机的freertos操作系统&#xff0c;将温湿度数据显示在oled屏幕上&#…...

华为云CTS 使用场景

云审计服务 CTS 云审计服务&#xff08;Cloud Trace Service&#xff09;&#xff0c;帮助您监控并记录华为云账号的活动&#xff0c;包括通过控制台、API、开发者工具对云上产品和服务的访问和使用行为&#xff0c;提供对各种云资源操作记录的收集、存储和查询功能&#xff0…...

【css】nth-child选择器实现表格的斑马纹效果

nth-child() 选择器可以实现为所有偶数&#xff08;或奇数&#xff09;的表格行添加css样式&#xff0c;even&#xff1a;偶数&#xff0c;odd&#xff1a;奇数。 代码&#xff1a; <style> table {border-collapse: collapse;width: 100%; }th, td {text-align: cente…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...