找环以及找环的入口
2016-08-04 本文已影响17人
IAmWhoAmI
![](https://img.haomeiwen.com/i2272026/5a3197521dab7cc9.png)
一个走一步,一个走两步
第一次就会相遇
![](https://img.haomeiwen.com/i2272026/612b75750f4b9105.png)
设置t 为走的次数
因为第一圈就会相遇:
则 t= L+x
2t = L + kn + x;
所以 t= kn;
L+x = kn
L = (k-1)n + (n-x)
所以出口就是一个从相遇点开始出发,
一个从链表头开始出发,
都走一步,遇到了就是了。
一个走一步,一个走两步
第一次就会相遇
设置t 为走的次数
因为第一圈就会相遇:
则 t= L+x
2t = L + kn + x;
所以 t= kn;
L+x = kn
L = (k-1)n + (n-x)
所以出口就是一个从相遇点开始出发,
一个从链表头开始出发,
都走一步,遇到了就是了。