JZ054-链表中环的入口节点

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

链表是由一系列连接在一起的结点构成，其中的每个结点都是一个数据结构。

这道题属于链表题型中等题目，思路如下：

题目未明确给出链表包含环，也就是说我们首先需要判断链表中是否存在环，如果存在然后再计算出环的入口。看到这个题我们直接用快慢指针进行解题：

第一步：定义慢指针p1，快指针p2；

第二步：p1一次走一步，p2一次走两步。直到p1 p2相遇后p2返回链表头结点，然后p2也降为慢指针， p1 p2在同时走；

第三步：p1 p2再次相遇后，返回该Node结点为入环结点；

疑问？

为什么用快慢指针可以判断单链表是否有环。

答：一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。

如何判断入口节点呢？

当快慢指针（slow、fast）相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n（n>=1）圈。假设slow指针走了s步，则fast指针走了2s步。同时，fast指针的步数还等于s加上在环上多转的n圈，设环长为r，则满足如下关系表达式： 

2s = s + nr; 
所以可知：s = nr; 
假设链表的头节点到“环的尾节点“的长度为L（注意，L不一定是链表长度），环的入口节点与相遇点的距离为x，链表的头节点到环入口的距离为a，则满足如下关系表达式： 
a + x = s = nr; 
可得：a + x = (n - 1)r + r = (n - 1)r + (L - a) 
进一步得：a = (n - 1)r + (L -a - x) 

那么可以得出结论： 
1. (L - a -x)为相遇点到环入口节点的距离，即从相遇点开始向前移动(L -a -x)步后，会再次到达环入口节点。 
2. 从链表的头节点到环入口节点的距离 ＝ (n - 1) * 环内循环 ＋ 相遇点到环入口点的距离。 
3. 于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

判断是否存在环：

求出环的入口：

       思考为什么他可以写出这么好的代码，把每道题的思路理解后用笔记本记录下来，争取刷到融会贯通，即看见有个题能自动归类到某个方面，这样有一定好处。面试最重要的是让面试官日后能愿意与你以后一起工作，因此沟通交流非常重要。比如有时候面试需要交流，看着像是一道排序的题做不出来，就可以跟面试官交流：“我有几个不成熟的想法，一排序，二动态规划，三是直接搜索算法”，面试官可能就给个提示：“你先用排序试试吧“。