专栏首页后端技术142. Linked List Cycle II

142. Linked List Cycle II

思路

首先要证明链表有环: 用快慢两个指针解决。快指针每次走两步,慢指针每次走一步。如果有环,则一定会最终在环内某点相遇。下面证明这一点:

假设慢指针进入环时,快指针在环内某点,且其前进方向与慢指针相差s步。那么根据运动规律,每次满指针走一步,快指针走两步,快、慢指针的距离会减少一步。所以,经过s轮,快指针一定会追上慢指针

IMG_20180920_160025.jpg

然后要找到环的入口

如上图,假设两个指针在某点相遇,则慢指针走了a + b步,快指针走了a + (b + c) + b + nr步(其中n>=0,环的长度是r,则b + c = r是一环的长度。快慢指针相遇时,快指针至少领先慢指针一环,所以有(b + c)) 由于快指针走了慢指针的两倍路程,有: 2(a + b) = a + (b + c) + b + nr 得: a = c + nrn>=0 所以a的长度比cn圈。

我们让一个指针从链表头开始,另一个指针从相遇点开始,每次各走一步,由于a = c + nr,当从链表头出发的指针经过a步到环入口时,从相遇点出发的指针先经过c步返回入口处,又绕着环走了n圈,依旧回到入口。所以两个指针一定会在环入口处相遇

如此,就找到环的入口了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • go 接口

    平凡的学生族
  • KafkaConsumer 入门理解

    需要理解offset的提交机制、保存。比如commitSync、commitAsync、__consumer_offsets。 深入还能了解offset的恢复...

    平凡的学生族
  • tomcat启动分析(5)Lifecycle、设计模式

    StandardServer直接继承了抽象父类LifecycleMBeanBase,从而间接继承了LifecycleBase,我们在LifecycleBase中...

    平凡的学生族
  • 基础知识 | 每日一练(59)

    士人有百折不回之真心,才有万变不穷之妙用。立业建功,事事要从实地着脚,若少慕声闻,便成伪果;讲道修德,念念要从虚处立基,若稍计功效,便落尘情。 ...

    C语言入门到精通
  • C语言指针5分钟教程

    指针、引用和取值 什么是指针?什么是内存地址?什么叫做指针的取值?指针是一个存储计算机内存地址的变量。在这份教程里“引用”表示计算机内存地址。从指针指向的内 存...

    猿人谷
  • 空指针 到底是什么意思?

    各位,前段时间我们有推文介绍过野指针和悬空指针,那C中还有一个叫做空指针的名词,它究竟是指什么呢,今天就跟大伙聊聊这个空指针。

    7089bAt@PowerLi
  • 视频流媒体平台编译中如何运用Go语言指针?

    本文讲的也是我们在编译流媒体平台EasyNVR的时候,碰到的go语言指针问题,就打算为大家介绍一下Go语言指针的运用。

    EasyNVR
  • Golang语言--指针

    在Go中指针是很容易学习的。一些进入编程任务,指针更容易操作,如通过引用调用,需要要使用指针来执行。所以学习指针成为完美Go程序员很有必要。让我们开始学习指针的...

    李海彬
  • 怎样熟练掌握C语言的指针?

    从事C语言开发已经超过10个年头,越来越觉得指针的方便之处,但在初学者来看指针就是拿下这门编程最大的拦路虎,毕竟很多人开始学习C语言都是激情四射结果遇上了指针猫...

    程序员互动联盟
  • C语言指针及占据内存空间

    我们可以把内存想象为成一列很长很长的货运火车,有很多大小相同的车厢,而每个车厢正好相当于在内存中表示一个字节。这些车厢装着不同的货物,就像我们的内存要存着各式各...

    诸葛青云

扫码关注云+社区

领取腾讯云代金券