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 Edge Case Check: If the head is null, return false (no cycle can exist in an empty list). Initialize Pointers: slow starts at head fast starts at head 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.

Mar 1, 2025 - 18:06

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

Edge Case Check: If the head is null, return false (no cycle can exist in an empty list).
Initialize Pointers:
- slow starts at head
- fast starts at head
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.