# Find the length of a Linked List which contains cycle (loop)

Technology CommunityCategory: Linked ListsFind the length of a Linked List which contains cycle (loop)
VietMX Staff asked 1 year ago
1. To find the length of loop apply Tortoise and Hare algorithm:
• Pointer A advances one (1) node a time.
• Pointer B advanced two (2) node a time.
• Start from head, they advanced at the same time until B hit null (no loop) or A and B point to the same node.
1. Now, has A advances only, A would meet B again. From that you can find the length of the loop say L.
2. Start from head again, this time have a pointer C advances L nodes first, followed by pointer D behind it, each advances one node at a time.
3. When they meet, the number of nodes D traveled L0 plus L is equal to the length of the linked list with a loop.
Implementation
package com.farenda.tutorials.algorithms.lists;

public class FloydCycleDetector {

private int position;
private int length;
private boolean cycle;

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;
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;
}
}