列表 环 判定 初始位置

判定的方法比较简单 有两种方法  

第1种是使用哈希表来存贮每个节点 这样的话 当hashset[ ] 中出现两个相同的节点时就能够判断出来这是1样的了  然后他所在的那个位置就是环第1次出现的位置上

第2种方法是用两个快慢指针来做  

设定两个指针分别为p1  p2   ，  p1的移动速度为每次移动1个距离   ，而p2的移动速度为每次移动两个距离  ，这样 ，直到快指针到达链表的结尾位置 

如果如果两个指针相遇的话  ，那就说明这个链表中存在环   ，没有相遇的话就没有存在环

可以想象  ，直到两个指针相遇，慢指针在环内的移动距离是不会超过环的长度 ，那极限来讲 如果链表是首尾相连的  那末 慢指针的移动距离正好为连表的长度  ，如果是1个小环的话，  那末 快指针也能够在慢指针没有走满半个圆环的时间内追上慢指针。

下面来讨论如何肯定初始位置的问题  设 连表出发点到环的初始位置的距离为a   p1和p2交点到环初始的位置为c （即p1在环内的移动距离为c） 环的长度为r  所以 对p1来讲  他所走过的路成为X = a + c   对p2来讲 他所走过的路程为       2X = a + c + k*r  （k的之不肯定 为自然数） 所以  x = k*r        如果让慢指针再走X步的话 他照旧会回到p1 与 p2相交的那个点  如果 让p2从连表的出发点开始走的话  每次移动两个距离  移动X次 他也会走到那个交点处  这样  当p2走完a个距离以后  就会与p1重合  共同在环里绕圈 知道走到交点   所以   这样就可以求出 环的初始位置了。

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠