一,问题
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出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
三,完整代码