# Problem Statement

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.

# Key Ideas

- Point 3 pointers to the head of the linked list — Slow pointer, fast pointer, and entry pointer.
- Move slow pointer 1 node at a time while moving fast pointer 2 nodes at a time
- At some point, both pointers will meet. At this moment, move entry pointer and slow pointer 1 node at a time.
- The node that entry pointer and slow pointer meet would be the cycle.

Look at the example below for a visualisation of the solution.

## Why? How? What??

Suppose that:

`a1`

is the length from head to start of cycle`a2`

is the length from start of cycle to where slow and fast pointers meet`a3`

is the remaining length — length from meeting point to start of cycle- So the distance that slow pointer travels is
`a1 + a2`

- We know that fast pointer moves twice as fast compared to slow pointer. So the distance travels is
`2 * (a1 + a2)`

. - We also know that fast pointer would have travelled through
`a3`

and come back to meet the slow pointer due to the cycle. So we can write our formula like so:`a1 + a2 + a3 + a2`

. There are 2`a2`

because fast pointer travels it twice. Remember that`a2`

is the length from start of cycle to where slow and fast pointers meet - So
`2 * (a1 + a2) = a1 + a2 + a3 + a2`

`(a1) + a1 + (a2) + (a2) = (a1) + (a2) + a3 + (a2)`

, cancel out the variable in bracket and we get`a1 = a3`

Now that we are equipped with this knowledge, we can write the code!

# Time and Space Complexity

## Time Complexity

The algorithm takes *O(N)* time because it traverse the linked list to find the cycle.

## Space Complexity

It runs in constant space *O(1)*