Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Floyd Cycle detection in Java

farenda 2017-05-13 0

One of the best known algorithms to detect a cycle in a linked list is Floyd Cycle detection. Using Floyd’s algorithm we can detect cycle, its beginning, and length.

Floyd Cycle detection algorithm is best know and very easy to implement. It consists of three parts:

  1. Cycle detection in linked list
  2. Finding start of the cycle/loop.
  3. Measuring length of the cycle/loop.

In the following sections we’re going to implement each part.

Definition of Node

In the examples we’ll use the following Node class as a basis of a linked list:

package com.farenda.tutorials.algorithms.lists;

public class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }
}

Nothing fancy, but enough to construct lists.

Cycle detection in linked list

The idea behind Floyd’s algorithm is straightforward. We go through the list in two speeds: by 1 node (slow as a tortoise), and jump every 2 nodes (jumps like a hare). Here’s the thing: when there is a cycle, the hare will eventually meet the tortoise. Let’s implement that.

Node tortoise = head;
Node hare = head;

boolean detectCycle() {
    // Empty and one element lists have no cycles:
    if (tortoise == null || tortoise.next == null) {
        return false;
    }
    // Keep going until there are elements in list:
    while (hare != null && hare.next != null) {
        // Advance both, but at their own speeds:
        tortoise = tortoise.next;     // 1 hop
        hare = hare.next.next;    // 2 hops
        if (tortoise == hare) {
            // hare can meet the tortoise only in a loop!
            return true;
        }
    }
    // hare found the end of the list, so no cycle:
    return false;
}

This story ends in two ways – either hare wins the race or both end up in the same position in a cycle. From now on we’ll consider only the second case.

Start of cycle/loop in linked list

TLDR: move tortoise to the beginning, then advance tortoise and hare at the same speed. The distance covered by the tortoise is the beginning of the cycle. The code is simple:

int findPosition() {
    int i = 1;
    tortoise = head;
    while (tortoise != hare) {
        tortoise = tortoise.next;
        hare = hare.next;
        ++i;
    }
    return i;
}

Why it works

After finding the cycle, the hare and the tortoise are at the same position in the cycle – the meeting point. Now we can define a few things:

  1. x – distance before entering the cycle.
  2. y – distance in the loop before the meeting point.
  3. z – distance between the meeting point and the beginning/end of the loop.

Having defined these variables we can calculate the following things:

  • tortoise distance before the meeting point = x + y
  • hare distance before the meeting = (x + y + z) + y = x + 2y + z
    Hare went through x, was in the loop sooner, therefore had to go through distance y once, then close the loop with distance z, and then again had to go through distance y to the meeting point.

Now, if the tortoise is at the beginning of the list, and the hare is at the meeting point. How can we know that advancing both at the same speed will make them meet at the beginning of the cycle? The distance covered by hare is twice of that covered by the tortoise. Therefore we can define the following equation:

2 * tortoise_distance = hare_distance
2 * (x+y) = x + 2y + z // from the above
2x + 2y = x + 2y + z
x = z

Math rules! :-)

Cycle/Loop length in linked list

Having the beginning of the loop, we can easily calculate it’s length by moving the hare or tortoise by 1 until they meet again:

int cycleLength() {
    int i = 0;
    do {
        hare = hare.next;
        ++i;
    } while (tortoise != hare);
    return i;
}

Complete Floyd Cycle Detector

All the above code can be gathered together into a simple Floyd Cycle Detector:

package com.farenda.tutorials.algorithms.lists;

public class FloydCycleDetector {

    private int position;
    private int length;
    private boolean cycle;
    private Node head, tortoise, hare;

    public void detect(Node head) {
        this.head = head;
        this.tortoise = this.hare = head;
        this.cycle = detectCycle();
        if (cycle) {
            System.out.println("Found cycle.");
            this.position = findPosition();
            this.length = cycleLength();
        } else {
            System.out.println("No cycle.");
            this.position = -1;
            this.length = 0;
        }
    }

    public boolean hasCycle() {
        return cycle;
    }

    public int length() {
        return length;
    }

    public int position() {
        return position;
    }

    private boolean detectCycle() {
        if (tortoise == null || tortoise.next == null) {
            return false;
        }
        while (hare != null && hare.next != null) {
            System.out.printf("(%d, %d),", tortoise.data, hare.data);
            tortoise = tortoise.next;
            hare = hare.next.next;
            if (tortoise == hare) {
                System.out.printf("turtle(%d) == hare(%d)%n",
                        tortoise.data, hare.data);
                return true;
            }
        }
        return false;
    }

    private int findPosition() {
        int i = 1;
        tortoise = head;
        System.out.printf("(%d, %d),", tortoise.data, hare.data);
        while (tortoise != hare) {
            tortoise = tortoise.next;
            hare = hare.next;
            ++i;
        }
        return i;
    }

    private int cycleLength() {
        int i = 0;
        do {
            hare = hare.next;
            ++i;
        } while (tortoise != hare);
        return i;
    }
}

Unit tests for Floyd Cycle Detector

package com.farenda.tutorials.algorithms.lists;

import org.junit.Test;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class FloydCycleDetectorTest {

    private FloydCycleDetector detector = new FloydCycleDetector();

    @Test
    public void nullIsNotCyclic() {
        detector.detect(null);
        assertFalse(detector.hasCycle());
        assertEquals(detector.position(), -1);
        assertEquals(detector.length(), 0);
    }

    @Test
    public void oneElementListShouldHaveNoCycle() {
        detector.detect(new Node(1));
        assertFalse(detector.hasCycle());
        assertEquals(detector.position(), -1);
        assertEquals(detector.length(), 0);
    }

    @Test
    public void shouldFindNoCycles() {
        detector.detect(createList(2));
        assertFalse(detector.hasCycle());

        detector.detect(createList(3));
        assertFalse(detector.hasCycle());
        assertEquals(detector.position(), -1);
        assertEquals(detector.length(), 0);
    }

    @Test
    public void shouldFindCyclesInOneLoopedNode() {
        Node head = new Node(1);
        head.next = head;

        detector.detect(head);

        assertTrue(detector.hasCycle());
        assertEquals(detector.length(), 1);
        assertEquals(detector.position(), 1);
    }

    @Test
    public void shouldFindCycleInMultiElementList() {
        Node head = createList(10);
        Node node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = head;

        detector.detect(head);

        assertTrue(detector.hasCycle());
        assertEquals(detector.length(), 10);
        assertEquals(detector.position(), 1);
    }

    private Node createList(int n) {
        Node head = new Node(1);
        Node node = head;
        for (int i = 2; i <= n; ++i) {
            node.next = new Node(i);
            node = node.next;
        }
        return head;
    }
}

References:

  • The Tortoise and Hare fable by Aesop :-)
  • Visual explanation of finding start of a loop
  • Check out other Algorithms and Data Structures!
Share with the World!
Categories Algorithms Tags algorithms, java, lists
Previous: Initialize Spring bean after construction
Next: Create Java Streams

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2021

sponsored
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.Ok