- 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.
- Now, has A advances only, A would meet B again. From that you can find the length of the loop say L.
- 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.
- 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;
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;
}
}