# 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

1. Point 3 pointers to the head of the linked list — Slow pointer, fast pointer, and entry pointer.
2. Move slow pointer 1 node at a time while moving fast pointer 2 nodes at a time
3. At some point, both pointers will meet. At this moment, move entry pointer and slow pointer 1 node at a time.
4. 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)

--

--

Software engineer in Singapore. Write random tech stuff. Still figuring out this “life” thing in life.