热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

快慢指针_快慢指针找链表中的环

本文由编程笔记#小编为大家整理,主要介绍了快慢指针找链表中的环相关的知识,希望对你有一定的参考价值。 
本文由编程笔记#小编为大家整理,主要介绍了快慢指针找链表中的环相关的知识,希望对你有一定的参考价值。



 





一、一定会相遇的证明

1、如果链表没有环,那么快指针比慢指针先到达尾部(null)

2、如果链表有环的话,因为快指针走的比慢指针快,所以在环中相遇的过程可以看作是快指针从环后边追赶慢指针的过程。

用递归法证明,快慢指针一定会相遇:

(1)快指针与慢指针之间差一步。此时继续往后走,慢指针前进一步,快指针前进两步,两者相遇。
(2)快指针与慢指针之间差两步。此时继续往后走,慢指针前进一步,快指针前进两步,两者之间相差一步,转化为第一种情况。
(3)快指针与慢指针之间差N步。此时继续往后走,慢指针前进一步,快指针前进两步,两者之间相差(N+1-2)即N-1步。重复这个过程,直到快指针和慢指针相遇。


因此,此题得证。所以快指针必然与慢指针相遇。


参考:
作者:知乎用户
链接:https://www.zhihu.com/question/23208893/answer/117115415

 

推导:慢指针进入环后,快指针最多多绕一个圈。

快指针F先进环,慢指针S后进。

假设慢指针进环那一刻快指针差m步能追上(0<= m 环),根据上边结论,两个指针走m次就会相遇了。

因为m 环,所以快指针在慢指针进环那一刻最多比慢指针多绕一个圈。

 


二、环长度

快指针和慢指针第一次相遇时的节点pq(碰撞点),快指针和慢指针从该点开始继续往前走,再次碰撞时所用的操作数就是环的长度Length

证明:由上边的推导可得,这里的m为Lengh

 


三、连接点

技术图片

 

假设慢指针进入环中时,即连接点p,快指针(q)需要m步才能追上慢指针。

p和q第一次相遇时,碰撞点在pq处。此时,p走到pq时用了m步。

 假设head到p的距离为a,环长度为Length,慢指针走了s步,则快指针走了2s步。

从上图可知:

s = a + m

2s = a + m + n * Length(n为快指针绕环的圈数)

可得

a = n * Length环 - m

也就是:若在头结点和相遇结点分别设一指针,同步(单步)前进,则最后一定相遇在环入口结点p。

可根据这个结论来找到入口节点。


四、带环链表总长度

找到连接点p后,求head到p的长度,再加上环的长度,即为链表的总长。




推荐阅读
  • 本文介绍了数据库的存储结构及其重要性,强调了关系数据库范例中将逻辑存储与物理存储分开的必要性。通过逻辑结构和物理结构的分离,可以实现对物理存储的重新组织和数据库的迁移,而应用程序不会察觉到任何更改。文章还展示了Oracle数据库的逻辑结构和物理结构,并介绍了表空间的概念和作用。 ... [详细]
  • 本文由编程笔记#小编为大家整理,主要介绍了logistic回归(线性和非线性)相关的知识,包括线性logistic回归的代码和数据集的分布情况。希望对你有一定的参考价值。 ... [详细]
  • 本文比较了eBPF和WebAssembly作为云原生VM的特点和应用领域。eBPF作为运行在Linux内核中的轻量级代码执行沙箱,适用于网络或安全相关的任务;而WebAssembly作为图灵完备的语言,在商业应用中具有优势。同时,介绍了WebAssembly在Linux内核中运行的尝试以及基于LLVM的云原生WebAssembly编译器WasmEdge Runtime的案例,展示了WebAssembly作为原生应用程序的潜力。 ... [详细]
  • 本文为Codeforces 1294A题目的解析,主要讨论了Collecting Coins整除+不整除问题。文章详细介绍了题目的背景和要求,并给出了解题思路和代码实现。同时提供了在线测评地址和相关参考链接。 ... [详细]
  • 微软头条实习生分享深度学习自学指南
    本文介绍了一位微软头条实习生自学深度学习的经验分享,包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性,并提供了一些建议。 ... [详细]
  • 阿里Treebased Deep Match(TDM) 学习笔记及技术发展回顾
    本文介绍了阿里Treebased Deep Match(TDM)的学习笔记,同时回顾了工业界技术发展的几代演进。从基于统计的启发式规则方法到基于内积模型的向量检索方法,再到引入复杂深度学习模型的下一代匹配技术。文章详细解释了基于统计的启发式规则方法和基于内积模型的向量检索方法的原理和应用,并介绍了TDM的背景和优势。最后,文章提到了向量距离和基于向量聚类的索引结构对于加速匹配效率的作用。本文对于理解TDM的学习过程和了解匹配技术的发展具有重要意义。 ... [详细]
  • Linuxchmod目录权限命令图文详解在Linux文件系统模型中,每个文件都有一组9个权限位用来控制谁能够读写和执行该文件的内容。对于目录来说,执行位的作用是控制能否进入或者通过 ... [详细]
  • Skywalking系列博客1安装单机版 Skywalking的快速安装方法
    本文介绍了如何快速安装单机版的Skywalking,包括下载、环境需求和端口检查等步骤。同时提供了百度盘下载地址和查询端口是否被占用的命令。 ... [详细]
  • 安装mysqlclient失败解决办法
    本文介绍了在MAC系统中,使用django使用mysql数据库报错的解决办法。通过源码安装mysqlclient或将mysql_config添加到系统环境变量中,可以解决安装mysqlclient失败的问题。同时,还介绍了查看mysql安装路径和使配置文件生效的方法。 ... [详细]
  • EPICS Archiver Appliance存储waveform记录的尝试及资源需求分析
    本文介绍了EPICS Archiver Appliance存储waveform记录的尝试过程,并分析了其所需的资源容量。通过解决错误提示和调整内存大小,成功存储了波形数据。然后,讨论了储存环逐束团信号的意义,以及通过记录多圈的束团信号进行参数分析的可能性。波形数据的存储需求巨大,每天需要近250G,一年需要90T。然而,储存环逐束团信号具有重要意义,可以揭示出每个束团的纵向振荡频率和模式。 ... [详细]
  • 在Android开发中,使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法,并提供了具体的代码实现。通过获取图片的宽高,计算目标宽度和高度,并创建新图实现等比例缩放。 ... [详细]
  • 本文介绍了在开发Android新闻App时,搭建本地服务器的步骤。通过使用XAMPP软件,可以一键式搭建起开发环境,包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表,并设置相应的属性。最后,给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]
  • 这是原文链接:sendingformdata许多情况下,我们使用表单发送数据到服务器。服务器处理数据并返回响应给用户。这看起来很简单,但是 ... [详细]
  • 向QTextEdit拖放文件的方法及实现步骤
    本文介绍了在使用QTextEdit时如何实现拖放文件的功能,包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数,并结合QMimeData和QUrl等类,可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]
  • 目录实现效果:实现环境实现方法一:基本思路主要代码JavaScript代码总结方法二主要代码总结方法三基本思路主要代码JavaScriptHTML总结实 ... [详细]
author-avatar
手机用户2502913375
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有