链表中环的入口节点(python)

一,问题

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

二,分析


首先要检查链表是否有环。

我们定义两个指针,一快一慢,规定快的每次能走两格,慢的只能走一格。如果快的先跑到了None,就说明链表无环。

如果快的和慢的相遇了,那么就说明有环

代码:

fast=pNode

slow=pNode

while fast and fast.next:

    fast=fast.next.next

    slow=slow.next

    if fast==slow:

        break

if fast==None or fast.next==None:

    return None 

判断有环之后,我们怎么去找那个环的起始点呢?

我们知道,快慢指针一定会在某点相遇

在这里我们假设环外的距离为m,环内从入口到相遇点的距离为d,剩下环内没走完的距离为p

由于快指针的速度是慢指针的2倍。我们设慢指针走了L,则快指针就走了2L

L=m+d

2L=m+n(p+d)+d=2(m+d)

p+d是一圈,不管fast套了slow几圈,都可以视为套了一圈。所以得到p+d=m+d

即p=m,也就是相遇点到环入口的距离 等于 环外起点到环入口的距离

这时将fast指针移回起始点

slow指针放在相遇点不动

让他们都只能一次走一格,在哪里相遇哪里就是入口点

 

 写代码:

fast=pHead

while fast!=slow:

    fast=fast.next

    slow=slow.next

return fast

三,完整代码

原文地址:https://www.cnblogs.com/buyaodong/p/13182283.html