判断单链表是否有环，并找出环的入口【python】

青旅半醒 2022-03-09 08:45 229阅读 0赞

# 转载：[https://blog.csdn.net/yangnianjinxin/article/details/79025768][https_blog.csdn.net_yangnianjinxin_article_details_79025768] #

2018年01月10日 16:52:24 [yangnianjinxin][] 阅读数：3498

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/yangnianjinxin/article/details/79025768

参考链接：

判断单向列表是否包括环，若包含，环入口的节点计算 python实现 - 鲸落丶 - 博客园 [https://www.cnblogs.com/kunpengv5/p/7784791.html][https_www.cnblogs.com_kunpengv5_p_7784791.html]

判断链表是否有环以及环的入口点(转载) - [天马行空][Link 1] - ITeye博客 [http://superwind.iteye.com/blog/706887][http_superwind.iteye.com_blog_706887]

问题：

**1、如何判断一个链表是不是这类链表？**

**2、如果链表为存在环，如果找到环的入口点？**

**一、判断链表是否存在环，办法为：**

设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)

二、找到环的入口点，方法：

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则 fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr s= nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

a + x = nr

a + x = (n – 1)r +r = (n-1)r + L - a

a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

易于理解的解释：

一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：

关于这个解法最形象的比喻就是在操场当中跑步，速度快的会把速度慢的扣圈

可以证明，p2追赶上p1的时候，p1一定还没有走完一遍环路，p2也不会跨越p1多圈才追上

我们可以从p2和p1的位置差距来证明，p2一定会赶上p1

但是不会跳过p1的 因为p2每次走2步，而p1走一步，所以他们之间的差距是一步一步的缩小，4，3，2，1，0 到0的时候就重合了

根据这个方式，可以证明，p2每次走三步以上，并不总能加快检测的速度，反而有可能判别不出有环

既然能够判断出是否是有环路，那改如何找到这个环路的入口呢？

解法如下：

当p2按照每次2步，p1每次一步的方式走，发现p2和p1重合，确定了单向链表有环路了

接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当p1和p2再次相遇的时候，就是环路的入口了。

这点可以证明的：

在p2和p1第一次相遇的时候，假定p1走了n步骤，环路的入口是在p步的时候经过的，那么有 p1走的路径： p+c ＝ n；

c为p1和p2相交点，距离环路入口的距离 p2走的路径： p+c+k\*L = 2\*n；

L为环路的周长，k是整数 显然，如果从p+c点开始，p1再走n步骤的话，还可以回到p+c这个点

同时p2[从头开始][Link 2]走的话，经过n步，也会达到p+c这点

显然在这个步骤当中p1和p2只有前p步骤走的路径不同，所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。

python 代码：

1.  `class Node(): #定义一个Node类，构造两个属性，一个是item节点值，一个是节点的下一个指向`
2.  `def __init__(self,item=None):`
3.  `self.item = item`
4.  `self.next = None`
5.   
6.  `def findbeginofloop(head):#判断是否为环结构并且查找环结构的入口节点`
7.  `slowPtr = head #将头节点赋予slowPtr`
8.  `fastPtr = head #将头节点赋予fastPtr`
9.  `loopExist =False #默认环不存在，为False`
10. `if head == None: #如果头节点就是空的，那肯定就不存在环结构`
11. `return False`
12. `while fastPtr.next != None and fastPtr.next.next != None: #fastPtr的下一个节点和下下个节点都不为空`
13. `slowPtr = slowPtr.next #slowPtr每次移动一个节点`
14. `fastPtr = fastPtr.next.next #fastPtr每次移动两个节点`
15. `if slowPtr == fastPtr : #当fastPtr和slowPtr的节点相同时，也就是两个指针相遇了`
16. `loopExist = True`
17. `print("存在环结构")`
18. `break`
19.  
20. `if loopExist == True:`
21. `slowPtr = head`
22. `while slowPtr != fastPtr:`
23. `fastPtr = fastPtr.next`
24. `slowPtr = slowPtr.next`
25. `return slowPtr`
26.  
27. `print("不是环结构")`
28. `return False`
29.  
30. `if __name__ == "__main__":`
31. `node1 = Node(1)`
32. `node2 = Node(2)`
33. `node3 = Node(3)`
34. `node4 = Node(4)`
35. `node5 = Node(5)`
36. `node1.next = node2`
37. `node2.next = node3`
38. `node3.next = node4`
39. `node4.next = node5`
40. `node5.next = node2`
41. `print(findbeginofloop(node1).item)`

扩展问题：

判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。

比较好的方法有两个：

一、将其中一个链表[首尾相连][Link 3]，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。

这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

[https_blog.csdn.net_yangnianjinxin_article_details_79025768]: https://blog.csdn.net/yangnianjinxin/article/details/79025768
[yangnianjinxin]: https://me.csdn.net/yangnianjinxin
[https_www.cnblogs.com_kunpengv5_p_7784791.html]: https://www.cnblogs.com/kunpengv5/p/7784791.html
[Link 1]: https://www.baidu.com/s?wd=%E5%A4%A9%E9%A9%AC%E8%A1%8C%E7%A9%BA&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[http_superwind.iteye.com_blog_706887]: http://superwind.iteye.com/blog/706887
[Link 2]: https://www.baidu.com/s?wd=%E4%BB%8E%E5%A4%B4%E5%BC%80%E5%A7%8B&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[Link 3]: https://www.baidu.com/s?wd=%E9%A6%96%E5%B0%BE%E7%9B%B8%E8%BF%9E&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd

发表评论取消回复

表情：

评论列表（有 0 条评论，229人围观）

还没有评论，来说两句吧...

相关阅读

相关单链表判断是否有环,并返回环的入口结点——java实现

单链表判断是否有环,并返回环的入口结点题目1 给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次

小咪咪/ 2024年03月17日 10:51/ 0 赞/ 64 阅读

相关 Java 判断单链表是否有环如果有环找到入口点

文章目录判断单链表是否有环如果有环找到入口点 1.判断单链表是否有环描述思路分析

痛定思痛。/ 2023年10月09日 13:45/ 0 赞/ 48 阅读

相关【Java数据结构】判断单链表是否有环，并且找出环的入口

一：判断是否有环思路：使用快慢引用法解决是否有环假设链表是一个有环链表，且由f指向c构成环。那么使用两个指针 A 和 B，让两指针同时向后遍历而且B的遍历速度

太过爱你忘了你带给我的痛/ 2023年02月26日 01:05/ 0 赞/ 3 阅读

相关判断链表是否有环、找到环的入口节点

昨天去完美笔试的时候遇到以前见过的老题目，记录一下吧... 题目很简单，就是说：给你一个链表，判断是否存在环！同时求出环的入口节点！

迈不过友情╰/ 2022年09月17日 12:23/ 0 赞/ 182 阅读

相关判断单链表中是否有环，找到环的入口节点

这类问题通常使用双指针的方法，即一个快指针一个慢指针。 faster = faster.next.next; slower = slower.next; “公理”：两指针

一时失言乱红尘/ 2022年05月24日 09:44/ 0 赞/ 194 阅读

相关如何判断一个单链表是否有环以及环入口

这是一个在我们学习数据结构的时候经常会遇到的问题，今天给大家带来这个问题的几种解法。方法一最容易想到的办法就是遍历单链表，如果单链表有环的话那么会进入死循环，但是我

太过爱你忘了你带给我的痛/ 2022年05月17日 02:24/ 0 赞/ 491 阅读

相关判断单链表是否有环，并找出环的入口【python】

转载：[https://blog.csdn.net/yangnianjinxin/article/details/79025768][https_blog.csdn.net_

青旅半醒/ 2022年03月09日 08:45/ 0 赞/ 230 阅读

相关测试单链表是否有环，并找到入口

<table style="border-collapse:collapse;"> <tbody> <tr> <td> <p style="line-heig

Dear 丶/ 2021年12月22日 09:17/ 0 赞/ 208 阅读

相关判断链表是否有环，有环则找到入口

设置两个指针p1,p2，p1每次走1步，p2每次走2步。当p2能与p1相遇，表明存在环。设p1走了S步，则p2走了2S步，又因为p2比p1多走了环的长度，即环的长度

你的名字/ 2021年09月26日 15:16/ 0 赞/ 351 阅读

相关【Java数据结构】判断单链表是否有环，并且找出环的入口

一：判断是否有环思路：使用快慢引用法解决是否有环假设链表是一个有环链表，且由f指向c构成环。那么

小鱼儿/ 2021年08月19日 12:52/ 0 赞/ 370 阅读