### Description

Given a linked list and return where the circle begins. For example, a linked list $[3, 2, 0, 4]$ having circle $[2, 0, 4]$ is shown below.

The algorithm should return the second node. I use C++ to solve this problem and define the node as below.

1 | //Definition for singly-linked list. |

### Solution 1: hashset

A trivial idea to solve this problem is saving the node information in a hashset when traversing and find if there is a visited node.

1 | class Solution { |

This is a method with O(n) time complexity and O(n) space complexity. But if there is a method to solve this problem with O(1) space complexity?

### Solution 2: fast and slow pointers

Set two pointers which slower one move one time one step and faster one move one time two steps. Once they meet, **reset the faster one to the head pointer**, then finally they will meet in the begin node of circle. This is an algorithm without extra space. But why it works?

There is a mathematical idea. Suppose the distance from head node to the begin of circle is $x_1$, the distance from begin of circle and meeting point on the circle is $x_2$, the distance from meeting point back to the begin of the circle is $x_3$. Then there is the velocity equation.

It means that the difference between $x_3$ and $x_1$ is the multiple of circle length. Due to the definition of $x_3$ and $x_1$, if the fast pointer move from the head node when the slow pointer move from the meeting point, **finally the slow pointer and fast pointer will meet on the begin of the circle.**

1 | class Solution { |

Don’t forget the special cases of NULL pointer and if fast pointer move to NULL means **there is no circle.**