一个链表中包含环,请找出该链表的环的入口结点。

图画的不错~~

一个链表中包含环,请找出该链表的环的入口结点。

思路:

X:链表头结点,Y:还入口结点,Z:第一次相遇结点

第一次相遇时slow走过的距离:a+b,fast走过的距离:a+b+c+b

fast走的距离是slow的2倍,2(a+b) = a+b+c+b,可以得到a=c(这个结论很重要!)

我们发现还的长度L=b+c=a+b,也就是说,从一开始到二者第一次相遇,循环的次数就等于环的长度

一个链表中包含环,请找出该链表的环的入口结点。