Cycle Detection in Linked Lists (Floyd’s Algorithm)

Cycle detection in a linked list is the process of determining whether the list contains a loop, where a node’s next reference points back to a previous node instead of null.

Floyd’s Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm, provides an efficient solution using constant extra space.

What Is a Cycle?

A cycle exists if, while traversing the list, you can return to a previously visited node.

Example:

1 → 2 → 3 → 4
      ↑     ↓
      └─────┘

In this list, node 4 points back to node 2, creating a cycle.

Why Cycle Detection Matters

Cycle detection is important for:

• Preventing infinite loops during traversal
• Debugging pointer-related bugs
• Detecting corruption in linked structures
• Implementing algorithms that rely on list termination

Floyd’s Algorithm (Tortoise and Hare)

Key Idea

Use two pointers moving at different speeds:

• Slow pointer (tortoise) moves one step at a time
• Fast pointer (hare) moves two steps at a time

If a cycle exists, the fast pointer will eventually catch up to the slow pointer.

Algorithm Steps

1. Initialize two pointers at the head
2. Move slow by one step and fast by two steps
3. If fast or fast.next becomes null → no cycle
4. If slow equals fast → cycle detected

Visual Intuition

Slow → 1 → 2 → 3 → 4 → ...
Fast → 1 → 3 → 1 → 3 → ...
           ↑
         meeting point

The difference in speed guarantees detection.

Rust Implementation

This implementation checks whether a cycle exists in a singly linked list.

// This method extends the existing SinglyLinkedList implementation.
// See the "Singly Linked List" section for the full Node and list definitions.

impl<T> SinglyLinkedList<T> {
    pub fn has_cycle(&self) -> bool {
        let mut slow = self.head.as_ref();
        let mut fast = self.head.as_ref();

        while let (Some(s), Some(f)) = (slow, fast) {
            // advance slow by 1
            slow = s.next.as_ref();

            // advance fast by 2
            fast = match f.next.as_ref() {
                Some(next) => next.next.as_ref(),
                None => return false,
            };

            if let (Some(slow_node), Some(fast_node)) = (slow, fast) {
                if std::ptr::eq(slow_node.as_ref(), fast_node.as_ref()) {
                    return true;
                }
            }
        }

        false
    }
}

Example Usage

fn main() {
    let mut list = SinglyLinkedList::new();

    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_back(4);

    // Manually create a cycle for demonstration
    if let Some(ref mut head) = list.head {
        let second = head.next.as_mut().unwrap();
        let tail = second.next.as_mut().unwrap().next.as_mut().unwrap();
        tail.next = Some(Box::new(Node {
            value: 2,
            next: None,
        }));
    }

    println!("Has cycle? {}", list.has_cycle());
}

In practice, cycles usually result from bugs rather than intentional construction.

Time and Space Complexity

Time Complexity

Space Complexity

Finding the Start of the Cycle (Conceptual)

Once a cycle is detected:

1. Move one pointer to the head
2. Move both pointers one step at a time
3. The meeting point is the start of the cycle

Limitations

• Only detects presence of a cycle
• Does not automatically remove the cycle
• Requires pointer access (not applicable to arrays)

Summary

• Cycles occur when a node points back to a previous node
• Floyd’s algorithm detects cycles efficiently
• Uses constant space and linear time
• One of the most elegant pointer-based algorithms

Playground Links

Rust - Floyd’s Algorithm