链表中环的入口结点 ​

题目： ​

一个链表中包含环，如何找出环的入口结点？

思路： ​

首先使用快慢指针的方式我们可以判断链表中是否存在环，当快慢指针相遇时，说明链表中存在环。相遇点一定存在于环中，因此我们可以从使用一个指针从这个点开始向前移动，每移动一个点，环的长度加一，当指针再次回到这个点的时候，指针走了一圈，因此通过这个方法我们可以得到链表中的环的长度，我们将它记为 n 。

然后我们设置两个指针，首先分别指向头结点，然后将一个指针先移动 n 步，然后两个指针再同时移动，当两个指针相遇时，相遇点就是环的入口节点。

详细资料可以参考： ​

• 《链表中环的入口结点》
• 《《剑指 offer》——链表中环的入口结点》