如何判断链表有环？

[hushicai]

原文地址：https://zhuanlan.zhihu.com/p/31401474

[hushicai]

在一个有环链表中，如何找出链表的入环点？

假设链表总长度为：L 表头到入环点的距离为：a 入环点到相遇点的距离为：x 环的长度为：r 相遇点到入环点的距离为：t

假设相遇时slow走了S步，则fast走了2S步。

2S = S + nr // 相遇时fast比slow在环内多跑了n圈。
S = a + x // 相遇时slow走过的步数
S = nr

从而得出：

a + x = nr
a + x = (n - 1)r + r = (n - 1)r + x + t 
a = (n - 1)r + t

所以，当fast再次从头出发，每次走一步 ，slow从相遇点出发，每次走一步，两者再次相遇时，即为入环点。

[hushicai]

判断两个单向链表是否相交，如果相交，求出交点。

先让计算链表的长度，让最长的链表A先走 len(A)-len(B)步，然后两个链表一起走，第一个相交点，即为所求的点。