# Floyd's Cycle Detection

## Concepts

Use a `slow` pointer and `fast` pointer to traverse over a graph/linkedlist, where `slow` moves by 1 whereas `fast` moves by 2 every round. Eventually, if there is a cycle in the graph/linkedlist, `fast` and `slow` will meet at some point, indicating that a cycle exists.

Think of them as two runners on a track: Since the fast runner runs exactly **twice** as fast as the slow runner, if there exists a cycle, the two runners will inevitably meet at some moment within the cycle.

<figure><img src="https://3155805757-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F8QWF60qHeGBho0id5iny%2Fuploads%2F6boXZ2u2CGdKReF2SHf0%2Fimage.png?alt=media&#x26;token=71e6d8f8-6530-49b8-ba1c-9c7421642a0e" alt=""><figcaption></figcaption></figure>

Floyd's Cycle Detection can find more information about the cyclic graph:

## Find Cycle Length

To find the cycle length, first find the meeting point where  `fast` and `slow` pointer collides. Then the cycle length can be found by running the `slow`pointer from that meeting point until it reaches back to itself.

## Find Cycle Starting Point

After the first collision/meet point of Floyd's Cycle Detection, we set one of the pointers back to the head of the whole list. Then, running both pointers at the same speed will cause them to meet again. That meeting point is exactly the entry point of the cycle. This image illustrates it well:

<figure><img src="https://3155805757-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F8QWF60qHeGBho0id5iny%2Fuploads%2FPCFWhkAo5MHIKKLulOgK%2Fimage.png?alt=media&#x26;token=f003a4fe-cde8-4f48-9b93-b736be38336f" alt=""><figcaption><p>From the Medium article introduced on top of this page</p></figcaption></figure>

## Problem:

{% embed url="<https://leetcode.com/problems/linked-list-cycle/description/>" %}
