漫画算法:如何判断链表有环?

大四毕业前夕,计算机学院,

正在四处求职的小灰碰到了同系的学霸大黄……

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%af%a2%e9%97%ae

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%8f%b9%e6%b0%94

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%af%a2%e9%97%ae2

%e5%b0%8f%e4%bb%93%e9%bc%a0%e6%b2%89%e6%80%9d

小灰边说边回忆着上周去面试的情形……

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%95%e5%ae%981

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%af%a2%e9%97%ae1

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%95%e5%ae%982

有一个单向链表,链表当中有可能出现“环”,就像下图这样。如何用程序判断出这个链表是有环链表?
%e9%93%be%e8%a1%a8%e5%9b%be1

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%8b%a6%e6%80%9d

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%9b%9e%e7%ad%942

方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的节点,就继续遍历下一个新节点,继续重复刚才的操作。

例如这样的链表:A->B->C->D->B->C->D, 当遍历到节点D的时候,我们需要比较的是之前的节点A、B、C,不存在相同节点。这时候要遍历的下一个新节点是B,B之前的节点A、B、C、D中恰好也存在B,因此B出现了两次,判断出链表有环。

假设从链表头节点到入环点的距离是D,链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 , 可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间,空间复杂度可以简单地理解成为O(1)。

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%95%e5%ae%983

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%8b%a6%e6%80%9d

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%9b%9e%e7%ad%943

方法二:首先创建一个以节点ID为键的HashSet集合,用来存储曾经遍历过的节点。然后同样是从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就用新节点和HashSet集合当中存储的节点作比较,如果发现HashSet当中存在相同节点ID,则说明链表有环,如果HashSet当中不存在相同的节点ID,就把这个新节点ID存入HashSet,之后进入下一节点,继续重复刚才的操作。

这个方法在流程上和方法一类似,本质的区别是使用了HashSet作为额外的缓存。

假设从链表头节点到入环点的距离是D,链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S,可以简单理解为O(N)。而算法的空间复杂度还是D+S-1,可以简单地理解成O(N)。

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%95%e5%ae%984

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%8b%a6%e6%80%9d

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%8b%a6%e6%80%9d2

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%95%e5%ae%980

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%a4%b1%e6%9c%9b

等通知就是没通知,这是职场上公认的语言。

以上就是小灰悲剧的回忆……

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%ae%b2%e8%a7%a31

%e5%b0%8f%e4%bb%93%e9%bc%a0%e6%b2%89%e6%80%9d2

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%ae%b2%e8%a7%a32

方法三:首先创建两个指针1和2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

例如链表A->B->C->D->B->C->D,两个指针最初都指向节点A,进入第一轮循环,指针1移动到了节点B,指针2移动到了C。第二轮循环,指针1移动到了节点C,指针2移动到了节点B。第三轮循环,指针1移动到了节点D,指针2移动到了节点D,此时两指针指向同一节点,判断出链表有环。

此方法也可以用一个更生动的例子来形容:在一个环形跑道上,两个运动员在同一地点起跑,一个运动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身后再次追上并超过,原因很简单,因为跑道是环形的。

%e8%b7%91%e9%81%93

假设从链表头节点到入环点的距离是D,链表的环长是S。那么循环会进行S*K次,K为正整数(为什么是S*K次,有心的同学可以自己揣摩下),可以简单理解为O(N)。除了两个指针以外,没有使用任何额外存储空间,所以空间复杂度是O(1)。

%e5%b0%8f%e4%bb%93%e9%bc%a0%e8%ae%b2%e8%a7%a30

问题一:判断两个单向链表是否相交,如果相交,求出交点。

%e9%93%be%e8%a1%a8%e5%9b%be3

问题二:在一个有环链表中,如何找出链表的入环点?

%e9%93%be%e8%a1%a8%e5%9b%be2

 

 

 

 

 

 

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%be%97%e6%84%8f

 

本人微信号:bjweimengshu

欢迎朋友们一起交流讨论,加好友请注明伯乐在线 :)

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

5 16 收藏 19 评论

关于作者:玻璃猫

互联网公司的码农一枚,喜欢算法和面向对象设计。个人微信号:13522239721 个人订阅号:dreamsee321欢迎一起交流讨论! 个人主页 · 我的文章 · 68 ·  

相关文章

可能感兴趣的话题



直接登录
最新评论
  • SHOHOKU   09/30

    一直数据结构和算法就不好,看了你的讲解明白了很多。谢谢楼主,已关注。望多出,我多学习

  • 另一个泰勒   10/01

    魏总?

  • good_water   10/02

    方法三楼主可以讲得再详细一点吗?本人愚笨,有点看不懂

    • 玻璃猫 程序员 10/04

      是这样,可以把带环的链表想象成一条直线跑道和一个环形跑道相连接。两个运动员从直线跑道起跑,一个跑得快,一个跑得慢。

      假设这个直线跑道前方没有环形,直接是终点,那么跑得快的运动员先跑道终点,跑得慢的运动员还在半路上,这时候证明链表没有环。

      假如这个直线跑道前方是环形跑道,那么跑得快的运动员会先一步进入环形跑道,沿着环形跑道无限转圈,跑得慢的运动员后进入环形跑道,因为两人的速度差,所以两人在环形跑道最终会相遇。这时候证明链表有环。

    • Arthas   10/10

      从物理角度来解释

      当慢指针速度为1,快指针速度为k,那步数应该是s/(k-1)向上取整,当快指针的速度为2的时候,循环次数即为S。

      以下是在下的一些想法如有错误敬请指出。 假设:从O点出发,链表循环交点为A,慢指针速度V1=1,快指针速度V2=kV1=k。L(OA)=D,L(AA')=S。移动N个节点花费的时间为t(),L()表示距离,AA'相当于从A点出发又回到A点即整个环的距离 当慢指针移动到点A的时候,快指针移动到点B,最后于点C相遇。 可得,时间t(OA)=L/V=D/1=D,L(OA)=D,L(OB)=kD,L(AB)=(k-1)D, 因为循环一周后必然相遇,设L(AC)=x,t(AC)=x/v1=x, L(快指针走过的距离)=L(BC)+S=L(AC)-L(AB)+S=V2*t=kx 得 x-(k-1)D+s=kx,x=s/(k-1)-D t(AC)=s/(k-1)-D,t(OA)=D t(OC)=t(AC)+t(OA)=s/(k-1),所耗时间即为循环次数。 进一步可以考虑,V2速度为多少的时候相遇的时间t最少,即慢指针从A点再移动1步就相遇, S1/V1=S2/V2,t1=S2/v2=(s1+BA')/V2=t1=1,V2=1+BA',k=1+S-(k-1)D;k=(1+D+S)/(1+D) 当D=1,S=8的时候,k=5可以的出s/(k-1)=2(取整)即从表头出发,2次就相遇。

  • 轻如纸张   10/02

    这两个问题的确算是在 LeetCode 上遇到的最匪夷所思的两道题了:Linked List Cycle & Intersection of Two Linked Lists 看到答案的感觉就是「还 TM 可以这样……」但总感觉是歪门邪道,不适合考察常规编程思维。

  • meta python,前端 10/04

    加波关注,温故知新,谢谢博主。

  • 熊猫Tony   10/06

    可以发一下后两个问题答案么?

    • ★小V★ 程序員 10/19

      那兩道題我就懶得發code了,想法告訴你一下,你可以試著把code寫出來

      第一道:找兩個鏈表(Linked List)的交點:

      提示:Loop一個Linked List, 記住最尾的Node,然後把最尾的Node的next連到下一個Linked List,弄成cycle,然後找Cycle就可以了

      第二道:循環起點

      還是動用2個指針的方法找Cycle,找到之後,把慢指針放在鏈表最前端,然後慢指針與快指針用同樣的速度前進,當慢指針的Node 等於快指針的Node的時候,就是這個Cycle的起點

      或許大家都很自然的認為在找Cycle的當中就找到cycle起點,然而這是不一定的,比如以下例子

      根據原文的方法的話,慢指針跟快指針分別就是這樣

      起點都在1 1

      2 3

      3 5

      4 7

      5 3

      6 5

      7 7

      然而很明顯的看出,起點應該在3

  • 厉害,我喜欢

  • 简简单单 IT 10/08

    这些面试题,感觉不是考面试者工作能力,而是随机应变能力吧?

    • 玻璃猫 程序员 10/10

      个人觉得算法主要是考察面试者的思维能力,但是个别题目第一次确实很难想到答案,需要多刷题。

  • 追梦   10/09

    生动形象,又有意思,楼主好思路,持续关注。

跳到底部
返回顶部