Detecting a Cycle in a Linked List Using Floyd’s Cycle Detection Algorithm

When working with linked lists, one common problem developers face is detecting whether the list contains a cycle. A cycle occurs when a node in the list points back to a previous node, forming a loop. This can lead to infinite loops and memory issues if not handled properly. In this blog post, we’ll explore an efficient solution to detect cycles in a linked list using Floyd’s Cycle Detection Algorithm, also known as the "Tortoise and Hare" approach.

Understanding the Problem

A singly linked list is a data structure where each node contains a value and a reference (or pointer) to the next node in the sequence. If a cycle exists, it means at least one node’s next pointer is pointing back to a previous node in the list instead of null (which typically signifies the end of the list).

Example of a Linked List with a Cycle

1 -> 2 -> 3 -> 4 -> 5
         ^         |
         |---------|

In the above example, node 5 points back to node 3, forming a cycle.

Solution: Floyd’s Cycle Detection Algorithm

Floyd’s algorithm is an efficient approach that uses two pointers:

• A slow pointer (moves one step at a time)
• A fast pointer (moves two steps at a time)

If the fast pointer eventually meets the slow pointer, a cycle exists. If the fast pointer reaches the end of the list (null), then there is no cycle.

Implementation in JavaScript

function detectACycle(head) {
    if (head == null) {
        return false;
    }
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (fast === slow) {  // Check after moving pointers
            return true;
        }
    }
    return false;
}

Explanation

1. Edge Case Check: If the head is null, return false (no cycle can exist in an empty list).
2. Initialize Pointers:
   • slow starts at head
   • fast starts at head
3. Loop Until Fast Meets Slow:
   • If fast or fast.next becomes null, return false (no cycle).
   • Move slow one step forward.
   • Move fast two steps forward.
   • If fast === slow, a cycle is detected.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes. Since the fast pointer moves twice as fast as the slow pointer, they will either meet or reach the end in linear time.
• Space Complexity: O(1) since we only use two pointers and no extra data structures.

Conclusion

Floyd’s Cycle Detection Algorithm is a simple yet powerful way to detect cycles in a linked list efficiently. By using two pointers moving at different speeds, we can determine whether a cycle exists without extra space. This technique is widely used in computer science and coding interviews.