算法记录

4

快慢指针:判断链表是否有环

slow在第一节点,fast在第二节点。slow每次前进一步,fast每次前进两步,如果链表有环的话,那么slow和fast必然在一个时间重合。

为什么在有环的情况下slow和fast就必然重叠?

我们假设fast在slow前面,它们之间的间距是N,则:

第一次:fast+2-slow-1=N;

第二次:fast+4-slow-2=N-1;

可见每次间距减少1,那么必然在某个时间点为0。(类似的,Vf-Vs=1即可)