题目(链表中换的入口节点)

题目：一个链表中包含环，请找出该链表的环的入口结点。

算法思路

算法主要分为两步走。

第一步需要判断链表是否有环。首先设置两个指针同时指向头结点，然后一个指针走一步，另一个指针走两步，如果他们能够相遇，那么说明该链表有环，并记录他们相遇的节点(相遇节点一定在环内),如果不存在这样的相遇节点，那么此链表无环。

第二步，需要找到链表中环的入口节点。首先需要根据相遇节点计算出此环中包含的节点个数 k，然后需要设置两个指针，其中一个指针先走 k 步，然后另一个指针再指向头结点；之后两个指针同时移动，直到他们相遇即都到达了环的入口节点，此时返回此节点。(后面寻找入口节点其实有点类似前一篇寻找链表中第 k 个节点的算法，仔细体会体会~)

算法实现

复杂度分析

代码只线性遍历链表，因此时间复杂度为 O(n)，空间复杂度O(1)。

参考

<<剑指offer2>>