找环以及找环的入口

2016-08-04  本文已影响17人  IAmWhoAmI
Paste_Image.png

一个走一步,一个走两步

第一次就会相遇

Paste_Image.png

设置t 为走的次数
因为第一圈就会相遇:
则 t= L+x
2t = L + kn + x;
所以 t= kn;
L+x = kn
L = (k-1)n + (n-x)

所以出口就是一个从相遇点开始出发,
一个从链表头开始出发,
都走一步,遇到了就是了。

上一篇 下一篇

猜你喜欢

热点阅读