Start of LinkedList Cycle

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)