算法记录
快慢指针:判断链表是否有环
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即可)
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即可)