CPPAlien / JS-QA

前端知识问答
0 stars 0 forks source link

算法 #44

Open CPPAlien opened 3 years ago

CPPAlien commented 3 years ago

单链表证明是否有环,并且找到环的入口?

成熟算法的快慢指针,两个指针从起点,一个每次前进一步,另一个每次前进两步,如果有环,则这两个指针必定相遇,相遇后,在用另一个指针从起点每次一步方式前进,原来的慢指针继续每次一步,相遇的那个节点则是环的入口。

1,首先我们要证明在一个环中,快慢指针一定会相遇,并且慢指针跑不完一圈。

快慢指针在一个环中快指针跨过慢指针而不相交的情况就是,前一步,他们两在同一个节点上,而此时他们就已经相遇了。所以慢指针一定会在一圈内被快指针追上。

2,接下来解析,为什么起点继续来个慢指针,两个慢指针同步走相遇的地方就是入口点。 2018111114523447 如图: 假设从起点到入口点的步数为:L 它们相遇的点距离入口点的步数为:b 从相遇点再到入口点的步数为:c 慢指针总共总了 i 步与 快指针相遇,则对应的快指针走了 2i,所以我们有以下等式

i = L + b
2*i = L + b + (b + c) * n // 由于快指针可能再遇到慢指针前已经走了 n 圈

则合并下两个等式

2 * (L + b) = L +b + (b + c) * n
          ||
          V
L + b = (b + c) * n
          ||
          V
L = (b + c) * (n - 1) + c

我们可以看出 b + c 就是一圈,而 L 的距离等于 n -1 圈加一个 c。所以说当另一个慢指针从起点继续出发,走了 L 后,不管这个慢指针走了多少圈,最终多走了 c 的距离,而此时他们正好会在入口处相交。