Detecting a Cycle in a Singly Linked List and Finding Its Start: Floyd's Cycle Detection Algorithm

Table of Contents

Problem Description Subproblem 1: Determine Whether a Linked List Contains a Cycle Subproblem 2: Find the Starting Point of the Cycle Solution Approach Phase 1: Floyd’s Cycle Detection (Determine Whether a Cycle Exists)Phase 2: Find the Entry of the Cycle (Mathematical Derivation)Mathematical Proof Code Implementation Illustrated Process Phase 1: Cycle Detection Phase 2: Find the Cycle Entry Complexity Analysis Key Takeaways Extended Thinking

1139 words

6 minutes

Detecting a Cycle in a Singly Linked List and Finding Its Start: Floyd's Cycle Detection Algorithm

2026-08-10

Algorithms

linked list

/

fast and slow pointers

/

Floyd's cycle detection

/

cycle detection

/

C

/

C++

/

JavaScript

Problem Description#

Subproblem 1: Determine Whether a Linked List Contains a Cycle#

Given the head node head of a singly linked list, determine whether a cycle exists in the linked list. If there is a node in the linked list that can be reached again by continuously following the next pointer, then a cycle exists in the linked list.

1
Input: head = 3→2→0→-4
2
              ↑_______↓
3
Output: true

Subproblem 2: Find the Starting Point of the Cycle#

Building on the previous problem, if a cycle exists, return the entry node of the cycle.

1
Input: head = 3→2→0→-4
2
              ↑_______↓
3
Output: node 2
4
Explanation: the entry of the cycle is node 2

Solution Approach#

Phase 1: Floyd’s Cycle Detection (Determine Whether a Cycle Exists)#

Use fast and slow pointers: slow moves one step at a time, fast moves two steps at a time.

If the linked list has no cycle: fast will reach null first, and we determine there is no cycle
If the linked list has a cycle: fast and slow will definitely meet in the cycle (just like on a circular track, the faster person will always lap the slower person)

Phase 2: Find the Entry of the Cycle (Mathematical Derivation)#

After fast and slow meet in the cycle:

Point slow back to the head of the linked list
slow and fast advance at the same speed (one step at a time)
The node where they meet again is the entry of the cycle

Mathematical Proof#

Let:

The distance from the head of the linked list to the cycle entry be a
The distance from the cycle entry to the first meeting point be b
The length of the cycle be L, then the remaining distance from the meeting point to the cycle entry is c = L - b

At the first meeting:

slow has walked a + b steps
fast has walked a + b + n·L steps (n is the number of extra laps fast has made)

Since fast’s speed is twice that of slow: 2(a + b) = a + b + n·L → a + b = n·L → a = n·L - b = (n-1)·L + (L - b) = (n-1)·L + c

a = c + (n-1)·L — This means that the distance of a steps from the head of the linked list to the cycle entry equals the distance of c steps from the meeting point to the cycle entry (possibly with a few extra laps).

Therefore, if we let slow start from the head and fast start from the meeting point, and both advance at the same speed, they will definitely meet at the cycle entry.

Code Implementation#

1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <stdbool.h>
4

5
typedef struct ListNode {
6
    int val;
7
    struct ListNode *next;
8
} ListNode;
9

10
/* Check whether a cycle exists */
11
bool hasCycle(ListNode *head) {
12
    ListNode *slow = head;
13
    ListNode *fast = head;
14

15
    while (fast && fast->next) {
16
        slow = slow->next;
17
        fast = fast->next->next;
18
        if (slow == fast) return true; // Fast and slow pointers meet, so a cycle exists
19
    }
20
    return false; // fast reaches the end, so there is no cycle
21
}
22

23
/* Find the entry node of the cycle */
24
ListNode* detectCycle(ListNode *head) {
25
    ListNode *slow = head;
26
    ListNode *fast = head;
27

28
    // Phase 1: Determine whether a cycle exists
29
    while (fast && fast->next) {
30
        slow = slow->next;
31
        fast = fast->next->next;
32
        if (slow == fast) {
33
            // Phase 2: Find the entry point of the cycle
34
            slow = head;
35
            while (slow != fast) {
36
                slow = slow->next;
37
                fast = fast->next;
38
            }
39
            return slow; // The meeting point again is the cycle entry
40
        }
41
    }
42
    return NULL; // No cycle
43
}

1
struct ListNode {
2
    int val;
3
    ListNode *next;
4
    ListNode(int x) : val(x), next(nullptr) {}
5
};
6

7
class Solution {
8
public:
9
    // Check whether a cycle exists
10
    bool hasCycle(ListNode *head) {
11
        ListNode *slow = head;
12
        ListNode *fast = head;
13

14
        while (fast && fast->next) {
15
            slow = slow->next;
16
            fast = fast->next->next;
17
            if (slow == fast) return true;
18
        }
19
        return false;
20
    }
21

22
    // Find the entry node of the cycle
23
    ListNode* detectCycle(ListNode *head) {
24
        ListNode *slow = head;
25
        ListNode *fast = head;
26

27
        // Phase 1: Determine whether a cycle exists
28
        while (fast && fast->next) {
29
            slow = slow->next;
30
            fast = fast->next->next;
31
            if (slow == fast) {
32
                // Phase 2: Find the entry point of the cycle
33
                slow = head;
34
                while (slow != fast) {
35
                    slow = slow->next;
36
                    fast = fast->next;
37
                }
38
                return slow;
39
            }
40
        }
41
        return nullptr;
42
    }
43
};

1
class ListNode {
2
    constructor(val) {
3
        this.val = val;
4
        this.next = null;
5
    }
6
}
7

8
// Check whether a cycle exists
9
function hasCycle(head) {
10
    let slow = head;
11
    let fast = head;
12

13
    while (fast && fast.next) {
14
        slow = slow.next;
15
        fast = fast.next.next;
16
        if (slow === fast) return true;
17
    }
18
    return false;
19
}
20

21
// Find the entry node of the cycle
22
function detectCycle(head) {
23
    let slow = head;
24
    let fast = head;
25

26
    // Phase 1: Determine whether a cycle exists
27
    while (fast && fast.next) {
28
        slow = slow.next;
29
        fast = fast.next.next;
30
        if (slow === fast) {
31
            // Phase 2: Find the entry point of the cycle
32
            slow = head;
33
            while (slow !== fast) {
34
                slow = slow.next;
35
                fast = fast.next;
36
            }
37
            return slow;
38
        }
39
    }
40
    return null;
41
}

Illustrated Process#

Phase 1: Cycle Detection#

1
Linked list: 3 → 2 → 0 → -4
2
           ↑__________↓
3

4
Step 1: slow=3, fast=3
5
Step 2: slow=2, fast=0
6
Step 3: slow=0, fast=2   ← fast has gone all the way around and lapped slow
7
Step 4: slow=-4, fast=-4 ← they meet at node -4! There is a cycle!

Phase 2: Find the Cycle Entry#

1
After the first meeting:
2
  slow resets to the head (3)
3
  fast stays at the meeting point (-4)
4

5
Advance at the same speed:
6
Step 1: slow=2, fast=2
7
        ↓       ↓
8
        The two meet at node 2 → node 2 is the entrance to the cycle!

Complexity Analysis#

Dimension	Analysis
Time Complexity	O(n) — slow walks at most n steps (from head to entry and then to the meeting point), each phase is O(n)
Space Complexity	O(1) — only two pointers are used

Key Takeaways#

The core of Floyd’s cycle detection is the speed difference: As long as fast is faster than slow (not necessarily 2x), and the speed difference is coprime with the cycle length, the cycle can be detected. Choosing 2x is the engineering-optimal practice.
The mathematical proof is an interview highlight: Being able to derive a = c + (n-1)·L is the key to distinguishing “memorizing templates” from “truly understanding.”
The elegance of the equal-speed return search: In the second phase, slow and fast walk at the same speed, and their meeting point is the entry — this is the most beautiful part of Floyd’s algorithm.

Extended Thinking#

If you need to calculate the length of the cycle, how would you do it? (After meeting, keep fast stationary, and let slow continue walking one full lap while counting)
Can the fast pointer move 3 steps at a time? What impact would that have?