Floyd Cycle Detection Algorithm in Java

(639 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 1 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Search


Search Tags

    Tortoise and the Hare algorithm in Java

    Java code for Floyd Cycle Detection Algorithm