python算法-014找出环的出口点（接013）

你今天晚了！
你看看现在几点了？

你的头发 。。

感谢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

感谢大家对我的监督，我会努力的，不管掉不掉头发！

加油！