Important announcement: Thank you for your clear testimonials. The copyright belongs to Chaoqun. I only forward, do not use for any commercial purposes.
Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.
Force button topic link
Here is the proof:
A The length from the beginning to the entrance of the ring
The length of the B ring
R the length traveled from the entry point during the first encounter
S1 = the length traveled by the slow pointer when a + x*b + r meet
S2 = the length of the fast pointer when a + y*b + r meets
According to the behavior of the fast and slow Pointers, 2*s1 = s2
So 2 times a plus xb plus r is equal to a plus yb plus r
We get 2 times a plus r minus a plus r is equal to y minus 2 times x times b
So a plus r is equal to b times y minus 2x.
A +r is an integer multiple of the ring length. When meeting for the first time, we walk r length from the entry point. According to the conclusion above, we can walk another A length to gather the ring length of integer times, that is, we reach the entry point.