Floyd’s Cycle Detect Algorithm: How to detect a Cycle (or Loop) in a Linked List?

Technology CommunityCategory: Linked ListsFloyd’s Cycle Detect Algorithm: How to detect a Cycle (or Loop) in a Linked List?
VietMX Staff asked 1 year ago

You can make use of Floyd’s cycle-finding algorithm, also known as tortoise and hare algorithm.

The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.

  • If the linked list has a loop they will definitely meet.
  • Else either of the two references(or their next) will become null.
Complexity Analysis

We only use two nodes (slow and fast) so the space complexity is O(1).

Implementation
boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while (fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops 

        if (slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}