【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
💓 博客主页:倔强的石头的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)...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

