Find Circle Entry for Linked List 博客分类： Algorithm algorithmlinked listcircle

The thinking about this question comes from Question 142 and 287 in LeetCode.

 

We all know that we can use two pointers to decide if there is a circle in a list:

fast: move 2 steps each time

slow: move 1 step each time

If slow meet fast in a certain moment, then this list has a circle.

 

Now I would like to show how we can find the entry of circle. Here is the demonstration:

 

 

 

First we define some variables:

s: when slow meet fast, the steps slow moves (so fast moves 2s steps)

x: the length from head to circle entry (this is what we  want to know)

c: the length of the circle

a: the length from entry points to meet points

we have: 2s = s + n*c (n is a positive integer)

                 s = x + a

so we have : x + a = n*c

                     x = (n-1)*c + c - a

c - a means the length from meet point to circle entry

we can consider the left side of expression as a new pointer who moves x steps from list head.

the right side: the slow moves n-1 circle plus the length from meet point to the entry.

 

So we can get the entry when new pointer meet slow.