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!
