当前位置：网站首页>为什么用快慢指针找链表的环，快指针和慢指针一定会相遇？

为什么用快慢指针找链表的环，快指针和慢指针一定会相遇？

2022-07-21 05:05:00 【大莲芒】

这个问题你可以用数学归纳法来思考。首先，由于链表是个环，所以相遇的过程可以看作是快指针从后边追赶慢指针的过程。那么做如下思考：

  1. 快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
  2. 快指针与慢指针之间差两步。此时唏嘘往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。
  3. 快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)-> N-1步。

因此，此题得证。所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。
在这里插入图片描述

原网站

版权声明
本文为[大莲芒]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_34574204/article/details/123077412

边栏推荐

猜你喜欢

随机推荐