【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
💓 博客主页:倔强的石头的CSDN主页
📝Gitee主页:倔强的石头的gitee主页
⏩ 文章专栏:《数据结构与算法 经典例题》C语言
期待您的关注
目录
一、问题描述
二、解题思路
方法一:数学公式推导法
方法二:转换为相交链表问题求解
三、代码实现
方法一实现代码
方法二实现代码
一、问题描述
原题链接 142. 环形链表 II - 力扣(Le142. 环形链表 II - 力扣(Le
二、解题思路
方法一:数学公式推导法
预备知识
此方法的数学推导建立在判断链表是否带环的基础算法上,推荐阅读前置文章
点击下方文字
【数据结构与算法 刷题系列】判断链表是否有环-CSDN博客
如图,通过快慢指针法得到两个指针相遇位置时
假设:
- 链表入环前的长度为L
- 环的长度为C
- 快慢指针相遇节点为meet
- 环的入口与相遇节点meet的距离为N
- 相遇时,快指针已经在环内走了X圈(X>=1,快指针至少比慢指针都走一圈才能追上)
推导过程:
在meet相遇点
慢指针移动距离为L+N
快指针移动距离为L+X*C+N
另外,快指针移动距离是快指针的两倍
快指针也可以写成2(L+N)
将两条公式结合起来
2(L+N)=L+X*C+N
化简
L+N=X*C
L=X*C-N
L=(X-1)*C+C-N
最终得到的公式:
L=(X-1)*C+C-N
该公式在图中说明的问题:
链表入环前的长度L
与相遇点到环入口的距离再加(X-1)圈 ——X最少为1,所以X-1至少为0
是相等的
结论:
如果两个指针分别从链表起始位置和相遇点meet开始移动,那么两个指针第一次相遇的节点就是环的入口
方法二:转换为相交链表问题求解
此方法的数学推到建立在判断链表是否带环的基础算法上,推荐阅读
【数据结构与算法 刷题系列】相交链表-CSDN博客
该方法是将带环链表问题转换为相交链表问题,将问题降级处理
首先,依然要 求得快慢指针相遇交点
然后将取得该节点下一个节点地址,令其成为一个单独链表的首节点,断开链表
之后,这个问题就可以转换为相交链表问题来解决
三、代码实现
方法一实现代码
struct ListNode {int val;struct ListNode* next;};
typedef struct ListNode ListNode;//方法一:数学推理法
struct ListNode* detectCycle1(struct ListNode* head)
{ListNode* slow, * fast;slow = fast = head;ListNode* meet = NULL;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast)//先求得快慢指针相遇节点{meet = slow;while (meet != head)//两指针同时移动,相遇即是入口{meet = meet->next;head = head->next;}return meet;}}return NULL;
}
方法二实现代码
//求相交链表的交点的函数
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{ListNode* pcurA = headA;ListNode* pcurB = headB;int countA = 0;int countB = 0;while (pcurA)//求出链表长度{pcurA = pcurA->next;countA++;}while (pcurB){pcurB = pcurB->next;countB++;}int tmp = abs(countA - countB);//长度差值ListNode* slow, * fast;if (countA < countB){slow = headA;fast = headB;}else{slow = headB;fast = headA;}while (tmp--)//长链表先走差值的步数{fast = fast->next;}while (fast && slow)//同步比较{if (fast == slow)return fast;fast = fast->next;slow = slow->next;}return NULL;
}
struct ListNode* detectCycle(struct ListNode* head)
{ListNode* slow, * fast;slow = fast = head;ListNode* meet = NULL;while (fast && fast->next){slow = slow->next;fast = fast->next->next;if (slow == fast)//先求得快慢指针相遇节点{meet = slow;ListNode* newhead = meet->next;meet->next = NULL;//将环断开,变成两个相交的链表return getIntersectionNode(head, newhead);}}return NULL;
}
总结
两种方法可以自行选用
第一种方法属于推理复杂,代码简单第二种方法属于推理简单,代码实现细节复杂
可根据实际情况选择合适的方法
相关文章:
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
💓 博客主页:倔强的石头的CSDN主页 📝Gitee主页:倔强的石头的gitee主页 ⏩ 文章专栏:《数据结构与算法 经典例题》C语言 期待您的关注 目录 一、问题描述 二、解题思路 方法一:数学公式推导法 方法…...
独立游戏之路:Tap篇 -- Unity 集成 TapTap 广告详细步骤
Unity 集成 TapADN 广告详细步骤 前言一、TapTap 广告介绍二、集成 TapTap 广告的步骤2.1 进入广告后台2.2 创建广告计划2.3 选择广告类型三、代码集成3.1 下载SDK3.2 工程配置3.3 源码分享四、常见问题4.1 有展现量没有预估收益 /eCPM 波动大?4.2 新建正式媒体找不到预约游戏…...
设计灵感源泉!7个令人赞叹的网页界面设计展示
网页的界面设计主要是指视觉设计和风格设计。高质量的界面更容易吸引用户的注意力,从而更准确地向用户传达信息。对于设计师来说,他们需要从高质量的作品中获得稳定的灵感,以帮助他们更高效地实现设计目标。在本文中,梳理了7个高质…...
vivado PIN
描述 引脚是基元或层次单元上的逻辑连接点。引脚允许 要抽象掉单元格的内容,并简化逻辑以便于使用。引脚可以 是标量的,包含单个连接,或者可以定义为对多个进行分组的总线引脚 信号在一起。 相关对象 引脚连接到一个单元,并且可以…...
docker部署mysql+nginx+redis
部署mysql 1、拉去镜像 docker search mysql docker pull mysql:5.7 2、运行镜像 docker run -p 3306:3306 --name mysql \ -v /home/mysql/log:/var/log/mysql \ -v /home/mysql/data:/var/lib/mysql \ -v /home/mysql/conf:/etc/mysql/conf.d \ -v /home/mysql/mysql-files…...
python文件操作、文件操作、读写文件、写模式
with读取文件数据内容 with open(filepath,mode,encoding) as file:#具体操作,例如:print(file.read())#查看文件所有的内容。 with:Python中的一个上下文管理器,用于简化资源的管理和释放。它可以用于任意需要进行资源分配和释放的情境…...
【亲测可用】docker进入正在运行的容器
微信公众号:leetcode_algos_life,代码随想随记 小红书:412408155 CSDN:https://blog.csdn.net/woai8339?typeblog ,代码随想随记 GitHub: https://github.com/riverind 抖音【暂未开始,计划开始】…...
线程池吞掉异常的case:源码阅读与解决方法
1. 问题背景 有一天给同事CR,看到一段这样的代码 try {for (param : params) {//并发处理,func无返回值ThreadPool.submit(func(param));} } catch (Exception e) {log.info("func抛异常啦,参数是:{}", param) } 我:你这段代码是…...
基于mysqlbinlog恢复数据
1、把binlog转换为SQL mysqlbinlog --base64-outputdecode-rows -vv /usr/local/mysql/log-bin/mysql-bin.000003 >result.sql find / -name result.sql 2、查看events show binlog events in mysql-bin.000003; 3、回滚到3667那一行的数据 mysqlbinlog -v /usr/local/mys…...
Android_Android Studio 常用快捷键 for mac
功能快捷键运行ctrl R优化importctrl opt O格式化opt cmd L自动修正opt enter自动补齐cmd J自动生成代码cmd N搜索使用到的地方fn opt F7 ( cmd)搜索使用到的地方2shift cmd F搜索类cmd O当前文件搜索cmd F全局搜索按两下 shift搜索文件shift cmd O搜索符号opt…...
[EFI]NUC11电脑 Hackintosh 黑苹果efi引导文件
硬件型号驱动情况主板 英特尔 NUC11DBBi9(LPC Controller WM590芯片组) 处理器 11th Gen Intel Core i9-11900KB 3.30GHz 八核 已驱动内存32 GB ( 三星 DDR4 3200MHz 16GB x 2 )已驱动硬盘三星 MZVL21T0HCLR-00B00 (1024 GB / 固态硬盘)已驱动显卡AMD R…...
在Ubuntu上配置和设置防火墙UFW
在本文我们学习如何在Ubuntu上配置和设置UFW(防火墙),UFW代表“不复杂的防火墙”,它充当IPTABLES的接口,从而简化了防火墙的配置过程,对于防火墙来说,这是非常困难的。初学者学习和配置防火墙规…...
nginx安装环境部署(完整步骤)
在部署nginx前,我们需要进行环境的部署 1.编译工具gcc,g,autoconf,automake ,make sudo apt-get install gcc g autoconf automake make 2.依赖库zlib,openssl,pcre 2.1 openssl下载地址 https://www.open…...
如何做电子骑缝章?
制作电子骑缝章的过程可以依据不同情况和所使用的工具而有所不同,但基本思路是确保印章能够跨过页面接缝,以验证文档的完整性。以下是几种常见的方法: 使用专业电子合同平台 选择平台:首先,确保你使用的电子合同平台…...
2024.6.13 bailuo-Docker 安装与镜像拉取
2024.6.13 bailuo-Docker 安装与镜像拉取 2024.6.12 bailuo-安装与镜像拉取 卸载 Docker 如果已安装旧版 Docker 则先卸载 yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-en…...
【Java开发规范】IDEA 设置 text file encoding 为 UTF-8,且文件的换行符使用 Unix 格式
1. IDEA 设置 text file encoding 为 UTF-8 file -> settings -> editor -> code style -> file encoding Transparent-native-to-asci conversion 要不要勾选?> 不推荐勾选(它的作用是用来自动转换ASCII编码,防止文件乱码&am…...
使用`LD_PRELOAD`和`jemalloc`实现C/C++信号的内存堆栈信息收集
文章目录 0. 概要1. 编译jemalloc2. 编译钩子共享库liballoc_hook.so3. 使用LD_PRELOAD加载钩子库liballoc_hook.so测试3.1 设置环境变量3.2 使用LD_PRELOAD加载钩子库并运行程序3.3 发送SIGUSR1信号以触发堆栈信息打印3.4 使用jeprof解析heap堆栈信息文件 4. 示例程序example.…...
计算机组成原理(四)Cache存储器
文章目录 Cache存储器的基本原理cache命中率、平均访问时间、效率地址映射全相联映射直接映射组相联映射 查找算法cache 存储器替换策略cache 存储器-写操作策略习题 Cache存储器的基本原理 Cache是一种高速缓冲寄存器,是为了解决CPU和主存之间速度不匹配而采用的一…...
怎么做成的文件二维码?扫阅览文件的制作方法
现在用二维码来分享或者查看文件是一种很常用的方式,比如常见的文件内容有简历、资料、作品、压缩包等等。通过将文件生成二维码能够在提升文件传输速度的同时还有利于用户体验的提升,那么如何制作可以长期提供文件预览或者下载的二维码呢? …...
js 前端 Function.prototype.call.call(0[‘toString‘], *, 16)
这个函数将 数组转任意进制 Function.prototype.call.call(0[toString], *, 16)...
李沐:用随机梯度下降来优化人生!
大侠幸会,在下全网同名「算法金」 0 基础转 AI 上岸,多个算法赛 Top 「日更万日,让更多人享受智能乐趣」 今天我们来聊聊达叔 6 大核心算法之 —— 优化 算法。吴恩达:机器学习的六个核心算法! 梯度下降优化算法是机器…...
Linux 环境.Net程序堆栈查询
# 安装 dotnet tool install --global dotnet-dump# 收集信息, 产生 core_XXX 文件 dotnet-dump collect -p pid# 分析 core_XXX 文件 dotnet dump analyze core_XXX# 列出 大于 XXX 字节的 对象 dumpheap -stat -min XXX# 查看对象具体信息 dumpobj address_XXX# 查看对应引用…...
志愿服务管理系统的设计
管理员账户功能包括:系统首页,个人中心,管理员管理,基础数据管理,广场论坛管理,志愿活动管理,活动报名管理 前台账户功能包括:系统首页,个人中心,志愿活动&a…...
微信小游戏5月畅销榜,新老产品更替显著,亿级爆款频出
小游戏由于微信的平台扶持,被视为可以大力发掘的蓝海,成为国内游戏最大的增长机会之一,随着越来越多的大厂和中小厂转向了小游戏赛道,每个月的小游戏畅销榜单都有不同变化。 5月的小游戏畅销榜显示,小游戏市场正经历显…...
自己想要公开自己的学习方法,但是自己很害怕自己的学习方法是一个错误的,因为对于自己而言,专升本的机会只有一次
分享自己的学习方法可能需要一定的勇气,特别是当你担心可能会受到批评或是不被理解时。以下是一些建议,可以帮助你克服这种恐惧:(kimi编辑器自己对于这些内容的基础批注) 自我肯定:首先,认识到你…...
linux centos consul1.15.2一键安装部署
consul原理、作用、安装相关内容 一、理论部分二、安装下载版本地址三、安装consul服务 一、理论部分 1、consul的原理 Consul的原理及作用可以归纳为以下几点: ①、基于Gossip协议的通信:Consul使用了基于Gossip协议的Serf实现来进行通信。 Gossip协议…...
速盾:dns和cdn区别?
DNS(Domain Name System)和CDN(Content Delivery Network)是互联网中两个不同但相互关联的服务。下面将详细解释DNS和CDN的区别。 功能和作用: DNS:DNS是将域名转换为IP地址的服务,它充当着互联…...
多目标跟踪中用到的求解线性分配问题(Linear Assignment Problem,LAP)C++
多目标跟踪中用到的求解线性分配问题(Linear Assignment Problem,LAP)C flyfish python实现,说的比这里详细 lapjv.h和lapjv.cpp代码在https://github.com/shaoshengsong/DeepSORT C代码调用 #include <iostream> #include <ve…...
Unity | Shader基础知识(第十四集:简单效果练习)
目录 前言 一、效果预览 1.弧形边缘光 二、效果制作 1. 制作弧形边缘光 2.弧形边缘光进阶 3.弧形边缘光调节渐变范围 4.边缘光突变 5.同心圆 三、加入世界坐标做效果 1.绘制结界 2.斑马球 3.效果合并 四、作者的碎碎念 前言 有粉丝建议说,让我继续更新…...
Vue48-ref属性
一、需求:操作DOM元素 1-1、使用原生的id属性 不太好! 1-2、使用 ref属性 原生HTML中,用id属性给元素打标识,vue里面用ref属性。 给哪个元素加了ref属性,vc实例对象就收集哪个元素!!࿰…...
高端定制网站开发设计建站流程/佛山关键词排名效果
发布时间:2016-03-13最终幻想14终于开测了!在小伙伴们说了这么长时间之后,7月22日开测时间已经到来了!众所周知,最终幻想14的地图非常大,所以在世界地图上,有着非常多的标志.今天小编为大家带来的就是地图上的红色圆球标志的作用介绍,我们一起 ...标签:游…...
只做硬件网站/seo攻略
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼/*************************************************************************************** 外部中断0实验 *实现现象:下载程序后按下K3按键可以对D1小灯状态取反。注意事项:无。***********************…...
网页制作培训苏州/seo公司网站
座位有限,礼品有限,所以大家快些去注册吧! 注册地址:http://www.msiw.net/Pages/EliteSummit2011.aspx 转载于:https://www.cnblogs.com/shangmeizhai/archive/2011/05/06/2038856.html...
网站建设与规划方案书/站长平台工具
2015年3月28日,在人来人往的北京中关村创业大街上的极客咖啡,近百位过去8年和InfoQ中国一同成长的朋友齐聚一堂,共同庆祝InfoQ中国(微信号:infoqchina)的八周年生日。\u0026#xD;\u0026#xD;时间回到2006年&a…...
网站的转盘游戏怎么做/个人网站设计
知乎的水印是如何批量添加的?您想拥有这个本领吗?我在opencv论坛发现了这个趣图添加logo的方法,也许您正需要这个代码,那我就诚心分享下吧。如何删除结果图像中mainlogo.png周围的黑色边框?import cv2 import numpy as np import…...
自己做的网站搜索不到/苹果要做搜索引擎
在判断一个网络的基本情况时,我们一般先在命令行下使用Ping命令,探测至目标地址的时延、丢包、MTU等情况。1、直接简单Ping测,可以查看时间和丢包情况2、使用-n参数,设置ping测包数量3、使用-t参数,一直Ping测…...