先来个图~
上结论,一个指针从链表的起始点出发,另一个指针从链表的相遇点出发,二者会在入环点相遇。
浅浅滴解释一下入换点与相遇点
入环点:指针开始进环后的第一个点
(2为入环点)
相遇点:slow指针与fast指针相遇(fast指针追上slow指针)的点
开始证明!
先介绍一下这个结论的背景,这里有一个slow指针,每次移动一步(slow=slow->next),还有一个fast指针,每次移动两步(fast=fast->next->next),fast指针会在环里面追上(相遇)slow指针。
证明:
注意:slow,fast进环后是按顺时针方向运动,相不相遇主要看的是二者间相对距离减少几,
例如slow每次走一步,fast每次走三步,那么它们每走一次相对距离减少二
距离:N N-2 N-4 N-6 二者是否相遇取决于N是奇数还是偶数,奇不遇偶遇
现在开始证明标题提到的结论