你今天晚了！
你看看现在几点了？
你的头发 。。
感谢425以及身边的同学，给我的动力，让我完成了今天的任务。今天就把找环出口给写了吧！
题目：给一个长度较大的链表，判断其是否有环存在，并找出环的出口点。例如：
H->1->3->4->6->7->0->2->4
1- ^ |
| 7
2- | |
| v
3- 7<-0<-2<-4<-3
这里说下为什么要找环的出口：因为如果链表有环，在遍历链表或者释放链表所占空间时，会很麻烦，如果我们知道了环的出口，就会变得很简单。
013的两种方法都可以实现判断是否有环，接下来就是找到环的出口，接着看着个字符图：
H->1->3->4->6->7->0->2->4
1- ^ |
| 7
2- | |
| v
3- 7<-0<-2<-4<-3
图中的节点6就是我们要找的出口。根据我们找环方式的不同，判断其出口就有略微的差别：
用蛮力法的话，在判断其是否相等时，就可以得到，相等的那个点就是我们要找的出口，返回这个节点就可以了。这代码简单，013代码加一行return 就能完成就不写了。
如果用快慢指针法，就有点差别。比如下面的情况：
f4
f1 f2
s6 s7
s1 s2 s3 s代表slow，f代表fast，
| | | 边上的数字代表遍历的次数
V V V
根据要求：每次遍历作比较
H->1->2->3 也就是遍历次数相同的作比较
^ | 我把s放在内层了，从图上来看，
| V 是在第5次遍历完成的判断，此时
5<-4 <—s4
^
|
s5
f3
f5
由此看来，这不是有点差别，差别还不小了。这还只是5个节点，那如果更大怎么办？
当有环时：
slow走的比fast慢，所以slow在与fast相遇时，slow一定没有遍历完链表，而fast已经进入环的循环，设slow遍历过了s个节点，则fast遍历了2s个。设fast在环里面转了n圈了，n>=1。设环的长度为r个节点，出口是第a个节点，当slow与fast相遇时的节点是第x个节点，链表长度为L。接下来就是数学题了，怎样解x？
高中数学学的不错的我，一眼看出了答案呢，你呢？
我大学学会了吹NB。。。
以下的推导过程还要感谢我的室友NJF同学：
fast走的步数还等于s+n*r，所以有：
2s=s+n*r=>s=n*r
又：a+x=nr
a+x=(n-1)*r+r=(n-1)*r+L-a
a=(n-1)*r+(L-a-x)
L-a-x为相遇点到环入口的距离
a=(n-1)*r+(L-a-x)这个式子的意义就是：链表头到环入口的距离=（n-1）*环长+相遇点到环入口的距离。
所以从链表头设一指针A，相遇点设一指针B，同时遍历，每次一步，必定相遇，且相遇点为入口点！
这太神奇了！感谢JF。
代码：
import random
import time
class LNode:
def __init__(self,arg):
self.data=arg
self.next=None
"""
题目描述：
链表中的某个节点的next域指向的是链表中在他之前的某一个节点，这样在链表尾部形成了环的结构。如何判断链表中是否有环的结构
要求：
方法：HashSet蛮力法
"""
def constructLinkwithAnnulation(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
n = random.randint(1, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
# 上面的部分 就是之前我们用的构造链表的方法
#这里我是设置了二分之一的概率产生有环的链表
if random.randint(0,1)==0:
m = random.randint(1, x - 1) # 用于选择出环的入口是哪个
Annulation=head.next # 用于遍历到选定的节点，就是出环的入口
while m>0:
Annulation=Annulation.next
m-=1
# 因为前面构造链表时就用了cur，最后他指向了最后一个节点
cur.next=Annulation #这里将尾结点的next域指向环入口
return head
def judgeAnnulation(head):
#判断链表是否为空
if head.next is None or head.next is None:
return None
#都指向第一个节点
slow=head.next
fast=head.next
#开始遍历
while fast is not None:
#这里注意一定先操作再判断，因为如果先判断的话，
# 第一个节点就是相等的
slow = slow.next
fast = fast.next.next
if slow==fast:
#这里直接判断两个节点是否完全相等,返回节点
return slow
return False
def Finddoor(head,meetNode):
A=head.next
B=meetNode
while A is not B:
A=A.next
B=B.next
return B
if __name__ == '__main__':
start = time.time()
head = constructLinkwithAnnulation(1000000)
end = time.time()
print("创建用时：", end - start)
cur = head.next
start1=time.time()
buer=judgeAnnulation(head)
end1=time.time()
print("判断用时：",end1-start1)
if buer == False:
print("head中没环")
elif buer==None:
print("head为空")
else:
print("head中有环,出口为：")
print(Finddoor(head,buer).data)
1000000
1000000
感谢大家对我的监督，我会努力的，不管掉不掉头发！
加油！
网友评论