Floyd Cycle Detection Algorithm in Java

(5322 Views)


What is Floyd Cycle Detection Algorithm?

Floyd’s Cycle Detection Algorithm is a pointer algorithm that makes use of only two pointers, which move through the given sequence at different speeds interval. The idea of algorithm is to move fast pointer twice as quickly as the slow pointer and the distance between the two increases by 1 at each step. If at some point both the points meet, we have a cycle in the list, else if we have reached the end of the list, no cycle is present. This algorithm is also called the “tortoise and the hare algorithm”.

Let's see a simple implementation of Floyd Cycle Detection Algorithm in Java.


tortoise and the hare Algorithm Implementation in Java

Node Class:

class node { int data; node next; public node(int data) { this.data = data; } public int getData() { return data; } public void setData(int data) { this.data = data; } public node getNext() { return next; } public void setNext(node next) { this.next = next; } }

Floyd's Algorithm:

void detectLoop(node first) { node slow = first; node fast = first; while (slow != null && fast != null && fast.getNext() != null) { slow = slow.getNext(); fast = fast.getNext().getNext(); if (slow == fast) { System.out.println("found loop"); return; } } System.out.println("loop not found"); }

Solution Worked 3 UpvotesUpvote

        

Solution Didn't Worked 1 DownvotesDownvote



Comments

2 comment
  • Admin

    Hello

  • Karlos

    Goodness, gracious it has been a long time since I have seen a Floyd circle detector. The algorithm is interesting purely due to its naivety. Even a deterministic Carson long chain discriminator will work more effectively than the Floyd detector.



Search

Play 2048 Game Online

Search Tags

    Tortoise and the Hare algorithm in Java

    Java code for Floyd Cycle Detection Algorithm