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

【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)

             💓 博客主页:倔强的石头的CSDN主页 

             📝Gitee主页:倔强的石头的gitee主页

   ⏩ 文章专栏:《数据结构与算法 经典例题》C语言

                                  期待您的关注

1b7335aca73b41609b7f05d1d366f476.gif

目录

一、问题描述

二、解题思路

方法一:数学公式推导法

方法二:转换为相交链表问题求解

三、代码实现

方法一实现代码

方法二实现代码


一、问题描述

原题链接   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;
}

总结

两种方法可以自行选用
第一种方法属于推理复杂,代码简单

第二种方法属于推理简单,代码实现细节复杂

可根据实际情况选择合适的方法

相关文章:

【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《数据结构与算法 经典例题》C语言 期待您的关注 ​ 目录 一、问题描述 二、解题思路 方法一&#xff1a;数学公式推导法 方法…...

独立游戏之路: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个令人赞叹的网页界面设计展示

网页的界面设计主要是指视觉设计和风格设计。高质量的界面更容易吸引用户的注意力&#xff0c;从而更准确地向用户传达信息。对于设计师来说&#xff0c;他们需要从高质量的作品中获得稳定的灵感&#xff0c;以帮助他们更高效地实现设计目标。在本文中&#xff0c;梳理了7个高质…...

vivado PIN

描述 引脚是基元或层次单元上的逻辑连接点。引脚允许 要抽象掉单元格的内容&#xff0c;并简化逻辑以便于使用。引脚可以 是标量的&#xff0c;包含单个连接&#xff0c;或者可以定义为对多个进行分组的总线引脚 信号在一起。 相关对象 引脚连接到一个单元&#xff0c;并且可以…...

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:#具体操作,例如&#xff1a;print(file.read())#查看文件所有的内容。 with&#xff1a;Python中的一个上下文管理器&#xff0c;用于简化资源的管理和释放。它可以用于任意需要进行资源分配和释放的情境…...

【亲测可用】docker进入正在运行的容器

微信公众号&#xff1a;leetcode_algos_life&#xff0c;代码随想随记 小红书&#xff1a;412408155 CSDN&#xff1a;https://blog.csdn.net/woai8339?typeblog &#xff0c;代码随想随记 GitHub: https://github.com/riverind 抖音【暂未开始&#xff0c;计划开始】&#xf…...

线程池吞掉异常的case:源码阅读与解决方法

1. 问题背景 有一天给同事CR&#xff0c;看到一段这样的代码 try {for (param : params) {//并发处理&#xff0c;func无返回值ThreadPool.submit(func(param));} } catch (Exception e) {log.info("func抛异常啦,参数是:{}", param) } 我&#xff1a;你这段代码是…...

基于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&#xff08;LPC Controller WM590芯片组&#xff09; 处理器 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&#xff08;防火墙&#xff09;&#xff0c;UFW代表“不复杂的防火墙”&#xff0c;它充当IPTABLES的接口&#xff0c;从而简化了防火墙的配置过程&#xff0c;对于防火墙来说&#xff0c;这是非常困难的。初学者学习和配置防火墙规…...

nginx安装环境部署(完整步骤)

在部署nginx前&#xff0c;我们需要进行环境的部署 1.编译工具gcc&#xff0c;g,autoconf&#xff0c;automake &#xff0c;make sudo apt-get install gcc g autoconf automake make 2.依赖库zlib&#xff0c;openssl&#xff0c;pcre 2.1 openssl下载地址 https://www.open…...

如何做电子骑缝章?

制作电子骑缝章的过程可以依据不同情况和所使用的工具而有所不同&#xff0c;但基本思路是确保印章能够跨过页面接缝&#xff0c;以验证文档的完整性。以下是几种常见的方法&#xff1a; 使用专业电子合同平台 选择平台&#xff1a;首先&#xff0c;确保你使用的电子合同平台…...

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 要不要勾选&#xff1f;> 不推荐勾选&#xff08;它的作用是用来自动转换ASCII编码&#xff0c;防止文件乱码&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是一种高速缓冲寄存器&#xff0c;是为了解决CPU和主存之间速度不匹配而采用的一…...

怎么做成的文件二维码?扫阅览文件的制作方法

现在用二维码来分享或者查看文件是一种很常用的方式&#xff0c;比如常见的文件内容有简历、资料、作品、压缩包等等。通过将文件生成二维码能够在提升文件传输速度的同时还有利于用户体验的提升&#xff0c;那么如何制作可以长期提供文件预览或者下载的二维码呢&#xff1f; …...

js 前端 Function.prototype.call.call(0[‘toString‘], *, 16)

这个函数将 数组转任意进制 Function.prototype.call.call(0[toString], *, 16)...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...