← Back to DSA Course | Chapter 4: Linked Lists | Lesson 5 of 8

Floyds Cycle Detection

In this page:

  1. Cycle in a List
  2. Floyd's Method
  3. Meeting Point
  4. Complexity
  5. Practical Use

Cycle in a List

A cycle exists in a linked list when following next pointers from some node eventually leads back to a node you've already visited, instead of ever reaching a null end, which would otherwise cause infinite traversal.

Example: Cycle in a List

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr};
    Node* b = new Node{2, nullptr};
    Node* c = new Node{3, nullptr};
    a->next = b; b->next = c; c->next = b;
    cout << "list has a cycle: node c points back to b, not to null" << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.next = c; c.next = b;
        System.out.println("list has a cycle: node c points back to b, not to null");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.next = c
c.next = b
print("list has a cycle: node c points back to b, not to None")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    struct Node *c = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2; c->data = 3;
    a->next = b; b->next = c; c->next = b;
    printf("list has a cycle: node c points back to b, not to NULL\n");
    return 0;
}

Floyd's Method

Floyd's algorithm, also called the tortoise and hare technique, uses two pointers moving through the list at different speeds: a slow pointer that advances one node at a time, and a fast pointer that advances two nodes at a time.

Example: Floyd's Method

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
bool hasCycle(Node* head) {
    Node* slow = head; Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
int main() {
    Node* a = new Node{1, nullptr}; Node* b = new Node{2, nullptr};
    a->next = b; b->next = a;
    cout << "has cycle: " << hasCycle(a) << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2);
        a.next = b; b.next = a;
        System.out.println("has cycle: " + hasCycle(a));
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

a, b = Node(1), Node(2)
a.next = b
b.next = a
print("has cycle:", has_cycle(a))
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int hasCycle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->next = b; b->next = a;
    printf("has cycle: %d\n", hasCycle(a));
    return 0;
}

Meeting Point

If there's no cycle, the fast pointer simply reaches the end (null) first. But if there is a cycle, the fast pointer eventually laps the slow pointer inside the loop and the two pointers land on the exact same node.

Example: Meeting Point

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr}; Node* b = new Node{2, nullptr}; Node* c = new Node{3, nullptr};
    a->next = b; b->next = c; c->next = b;
    Node* slow = a; Node* fast = a;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) { cout << "met at node with data " << slow->data << endl; break; }
    }
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.next = c; c.next = b;
        Node slow = a, fast = a;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) { System.out.println("met at node with data " + slow.data); break; }
        }
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.next = c
c.next = b
slow = fast = a
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        print("met at node with data", slow.data)
        break
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    struct Node *c = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2; c->data = 3;
    a->next = b; b->next = c; c->next = b;
    struct Node *slow = a, *fast = a;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) { printf("met at node with data %d\n", slow->data); break; }
    }
    return 0;
}

Complexity

Because the fast pointer only ever needs to traverse the list a bounded number of times, Floyd's algorithm detects a cycle in O(n) time while using just two pointer variables, so it needs O(1) extra space.

Example: Complexity

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
bool hasCycle(Node* head) {
    Node* slow = head; Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
int main() {
    Node* a = new Node{1, nullptr}; Node* b = new Node{2, nullptr};
    a->next = b; b->next = a;
    cout << "O(n) time, O(1) space -- only two pointers used: " << hasCycle(a) << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2);
        a.next = b; b.next = a;
        System.out.println("O(n) time, O(1) space -- only two pointers used: " + hasCycle(a));
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

a, b = Node(1), Node(2)
a.next = b
b.next = a
print("O(n) time, O(1) space -- only two pointers used:", has_cycle(a))
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int hasCycle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->next = b; b->next = a;
    printf("O(n) time, O(1) space: %d\n", hasCycle(a));
    return 0;
}

Practical Use

This technique isn't limited to linked lists; the same slow/fast pointer idea detects cycles in any structure where you repeatedly follow a next relationship, such as detecting a loop in a sequence of function calls or states.

Example: Practical Use

#include <iostream>
using namespace std;
int nextInSequence(int n) {
    int sum = 0;
    while (n) { int d = n % 10; sum += d * d; n /= 10; }
    return sum;
}
int main() {
    int slow = 19, fast = 19;
    do {
        slow = nextInSequence(slow);
        fast = nextInSequence(nextInSequence(fast));
    } while (slow != fast);
    cout << "cycle detected in number sequence at value " << slow << endl;
    return 0;
}
public class Main {
    static int nextInSequence(int n) {
        int sum = 0;
        while (n > 0) { int d = n % 10; sum += d * d; n /= 10; }
        return sum;
    }
    public static void main(String[] args) {
        int slow = 19, fast = 19;
        do {
            slow = nextInSequence(slow);
            fast = nextInSequence(nextInSequence(fast));
        } while (slow != fast);
        System.out.println("cycle detected in number sequence at value " + slow);
    }
}
def next_in_sequence(n):
    total = 0
    while n:
        d = n % 10
        total += d * d
        n //= 10
    return total

slow = fast = 19
while True:
    slow = next_in_sequence(slow)
    fast = next_in_sequence(next_in_sequence(fast))
    if slow == fast:
        break
print("cycle detected in number sequence at value", slow)
#include <stdio.h>
int nextInSequence(int n) {
    int sum = 0;
    while (n) { int d = n % 10; sum += d * d; n /= 10; }
    return sum;
}
int main() {
    int slow = 19, fast = 19;
    do {
        slow = nextInSequence(slow);
        fast = nextInSequence(nextInSequence(fast));
    } while (slow != fast);
    printf("cycle detected in number sequence at value %d\n", slow);
    return 0;
}
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Linked List Reversal Next Lesson → Merge Two Sorted Lists

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.