纵有疾风起
人生不言弃

环的问题:操场上,如何多次偶遇女神?

前言

一个风清月皎的夜晚,小莱独自在操场漫步。突然一个熟悉的身影从旁边经过,小莱定睛一看,这不是心怡很久的女神吗?小莱快走几步追上女神后打了个招呼就径直往前走了(没出息)。为了加深女神对自己的印象,小莱决定再来一次偶遇(回头是不可能回头的)。只见小莱加快了步伐,终于再次偶遇到了自己的女神…..

本期主要分为以下几个部分:

判断是否有环

环的长度

环的入口

链表长度

画外音:关于单链表知识,请点击回顾

判断是否有环

环的问题:操场上,如何多次偶遇女神?插图

如图,这是一个链表存在环的示意图。

我们如何来判断是否有环呢?小莱偶遇女神的例子或许对我们有所启发。

环的问题:操场上,如何多次偶遇女神?插图(1)

在A点小莱和女神第一次相遇(起点)。

环的问题:操场上,如何多次偶遇女神?插图(2)

为了再次相遇,小莱在女神保持速度不变的情况下,采取了加(风)快(驰)步(电)伐(掣)的策略。由于操场是个环形,那么在两个人一快一慢的场景下必然会再次相遇,于是在B点小莱又遇到了自己的女神。

画外音:操场上想尽快遇到妹子,横穿草坪超近道也是可以的哈!

那么结合到链表里如何处理呢?接下来我们的主角就该登场了:

「 快慢指针 」

在链表环的问题中我们常常用快慢指针来进行处理,即设置slow、fast两个指针变量(slow可以看作女神,fast可以看作小莱):

slow每次走一步,即slow->next;

fast每次走两步,即fast->next->next;

如果slow和fast相遇的话,即可以判断当前链表中有环。

代码实现:

环的问题:操场上,如何多次偶遇女神?插图(3)

环的长度

既然知道了链表中有环,那么如何计算这个环的长度呢?

小莱和女神在B点相遇了,那么女神按照小莱的轨迹走一遍再回到B点,行走的路程不就是环的长度吗?

画外音:真他娘的聪明。

代码实现:

环的问题:操场上,如何多次偶遇女神?插图(4)

p节点用来记录B点的位置。

环的入口

环的问题:操场上,如何多次偶遇女神?插图(5)

如图所示,现在我们想要知道环的入口位置。

假设 A到C的距离为x,C到B的距离为y,环的长度为r。在B点相遇时,女神走的距离为s,那么小莱的距离则为2s(速度是女神的2倍)。

那么可以根据:

s = x + y;2s = x + y + n * r;

推导出:

x = n * r – y;

画外音:n表示相遇时快指针(小莱)比慢指针(女神)多走的环数。

根据这个公式,我们可以设置两个指针,一个在相遇点B,一个在起点A,然后两个指针同时走(每次走一步),当这两个指针相遇时,此时的位置即为环的入口点。

环的问题:操场上,如何多次偶遇女神?插图(6)

链表长度

进行到这里,链表长度的问题就简单的多了。

环的问题:操场上,如何多次偶遇女神?插图(7)

根据前面两步,我们知道了环的长度r,同时在获取环的入口时可以计算出起始点到入口的距离x。那么链表的长度L就很容易得出来了。

链表长度L =  起始点到入口的长度x + 环的长度y

我目前是在职前端开发,会前端,懂java,知Python,如果你现在也在学习前端,了解前端,渴望成为一名合格的前端开发工程师,在入门学习前端的过程当中有遇见任何关于学习方法,学习路线,学习效率等方面的问题,你都可以申请加入我的前端学习交流群:518672693。里面聚集了一些正在自学前端的初学者,群文件里面还有我整理的一些不错的前端学习手册,前端面试题,开发工具和PDF文档书籍教程,需要的话都可以自行来获取下载。

文章转载于:https://www.jianshu.com/p/5e7d2559fba9

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 环的问题:操场上,如何多次偶遇女神?

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活