一个链表中包含环,请找出该链表的环的入口结点。
图画的不错~~
思路:
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,也就是说,从一开始到二者第一次相遇,循环的次数就等于环的长度
图画的不错~~
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,也就是说,从一开始到二者第一次相遇,循环的次数就等于环的长度