题目：已知一个链表有环，求环的入口
链表有环，所以让一个快指针，一个慢指针，同时从起点出发，他们必定在环中相遇。而且相遇的时候，慢指针必定只走了环的不到一圈。(为什么可以自己想。其实可以反推，如果相遇点是慢指针第二次走过的时候，那么第一次走过环中此点和第二次走过环中此点期间，快指针肯定走过不止一圈，所以应该在其他的地方早就相遇了，所以假设不成立。)
假设一个慢指针以速度v从起点开始走，一个快指针以速度2v从起点开始走，在环中某个点相遇。
设起点到环入口的距离为x，环入口到相遇点的距离为y，环的长度为L，那么：
vt = x+y
2vt=x+y+nL
得到x+y = nL
即x = nL-y，发现了没有
相遇点在距离环入口y，那么走nL-y就又走到了环入口。
还没有思路吗。。。
慢指针和快指针相遇后，慢指针以速度v再从起点出发，快指针降速，也以速度v，不过是从相遇点出发，
当慢指针走过x的距离的时候，快指针走过了nL-y(因为他们速度一样，且有关系式x = nL-y)，此时看快指针到哪了？
快指针从距离环入口y的地方出发，走过了nL-y，你说快指针到了哪？？？当然是又回到了环入口了啊。。。。
慢指针从起点走过了x，说明慢指针也走到了环的入口了啊。。。。
说明什么？？？还在蒙圈中吗。。。
说明他们相遇了啊，而且相遇的地方，恰好就是环的入口啊。。。
估计还在懵逼中。。。
网友评论