There are links in the linked list. Can you walk three steps faster or slower

Let's start with the results , You can take three steps , But it is not necessary to , It's going to affect efficiency .

Here's the derivation process , Excerpt from stackflow.

Let the non ring part s Step , Ring t Step , A fast pointer is a slow pointer k times , The speed pointer is at the beginning of the distance ring j Meet at step .

that , When we met , Slow down s+j, It's almost gone s + j + m * t,（m Is the number of turns of the fast pointer in the ring ）

here , The distance of the fast pointer is slower than that of the slow pointer k times , There is an equation ：

k * (s + j) = s + j + m * t

Change it. ：

s + j =  (m / k-1)t

According to the above formula , On the left side of the equation is the number of steps taken by the slow pointer , Is a multiple of the length of the ring on the right side of the equation , Slow pointer steps s + j Is an integer , Ring length t It's also an integer ,(m / k-1) in ,k-1>0, When other quantities are determined , keep (m / k-1) If it doesn't change , The denominator k-1 The smaller it is , Then molecule m The smaller , Corresponds to the number of turns the fast pointer travels in the ring m The smaller ,k=2,3,4···, among k=2 when ,m Minimum , That is, the fastest meeting , This is the most efficient .

Ring linked list entry point

leetcode142 topic ：https://leetcode.cn/problems/linked-list-cycle-ii/
You can also deduce .
How many steps does the fast and slow pointer take ：f=2(s+j)
When the fast and slow pointers meet ,f=(s+j) +mt（ The meaning of the formula is the same as the top ）
Then we can get s+j=mt, The number of turns around when meeting is just equal to the number of steps taken by the slow pointer .
Suppose you leave at this time l Step to the entrance of the ring , Will and go s The pointer of the step meets , Yes mt+l=mt+s ( Ring plus mt Or the origin ）
After combining the above two formulas, we get l=s, That is, go to the non ring part s Step to the entry point .

Pictured , After purple nodes meet , Suppose the fast pointer goes around here again , go b+c, And the slow pointer goes here , go a+b, among b For the public part , be a=c.

summary ： When we met , The number of steps taken by the slow pointer is exactly the total number of steps taken by the fast pointer in the ring , The number of steps from the entry point is exactly the number of non loop path steps .

Reference link ：https://stackoverflow.com/questions/5130246/why-increase-pointer-by-two-while-finding-loop-in-linked-list-why-not-3-4-5