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:

- Cycle detection in linked list
- Finding start of the cycle/loop.
- 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:

**x**– distance before entering the cycle.**y**– distance in the loop before the meeting point.**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!