如何判断链表有环以及求入环节点

转载自：http://blog.csdn.net/elicococoo/article/details/51173166

如何判断单链表有环，并找出环的入口？ 

时间O(n)，空间O(1)。 

这个面试题还是蛮有趣的，当时只想出了第一问，第二问实在巧妙。 

如图这个单链表，蓝色的部分是环。 

对于如何判断链表有环，可以从起点发出两个指针，一个一次一步，另一个一次两步，如果两个指针相遇，那么这个单链表就有环。 

设绿色的地方是指针相遇点。 

对于第二问求环的入口，从第一问的相遇点和起点各发出一个速度为一步的指针，两个指针相遇的地方就是环的入口。 

这个是别人给我的答案，我简单推了一下公式好像是对的，但是实践了后又发现好像有点细节问题，这里留下我的答案： 

第一问得出相遇点后，再发出一个指针，统计这个指针再次回到这个点的距离，也就是环的距离。 

然后从起点再发出两个指针，一个指针在另一个前面，两个指针的距离就是环的距离，当两个指针再次相遇的时候就是环的入口。

下面补充一下计算入环节点的过程：

 1）首先判断是否有环,有环时，返回相遇的节点，无环，返回null

 * 2）有环的情况下， 求链表的入环节点

 *   fast再次从头出发，每次走一步，

 *   slow从相遇点出发，每次走一步，

 *   再次相遇即为环入口点。