# Floyd's cycle detection algorithm in linked list

I am doing interview studying and would like to have another look at my implementation of Floyd's cycle detection algorithm.

I've implemented a simple linked list which can be fluently configured and works generally for any type on stack. The cycle detection method serves:

• to find if there are any cycles in list or return Optional.empty()
• to return the start node value of the cycle, if there is any

A cycle should be found in worst-case O(n) time complexity and O(1) space consumption. The same applies for retrieving the cycle start node.

Apart from correctness, I've strived for client simplicity, null-safety and clarity - would like to hear thoughts on how to improve this code and/or add more test cases.

Here is the data structure:

public class CyclicLinkedList<T> {

private Builder.Node<T> first;
private int count = 0;

public static <T> AddNext<T> builder() {
}

public Optional<T> firstNodeInCycle() {
if (count < 2) return Optional.empty();
Builder.Node<T> slow = first;
Builder.Node<T> fast = first;

while (true) {
if (fast == null) return Optional.empty(); // if fast reaches end, no cycle
fast = fast.next; // advance fast one more step
if (fast == null) return Optional.empty(); // again check if fast reached end - if it does, no cycle
fast = fast.next; // advance both one step
slow = slow.next;
if (fast.index == slow.index) { // if fast and slow are equal, that can only mean fast has reached slow from behind, thus proving cycle
slow = first;
while (true) { // find the starting point of the cycle
if (fast.index == slow.index) return Optional.of(slow.item);
slow = slow.next;
fast = fast.next;
}
}
}
}

private boolean isEmpty() {
return count == 0;
}

public interface AddNext<T> {

Build<T> defineCycleOrBuild();
}

public interface Build<T> {
Build<T> connectLastTo(int index);

}

private static class Builder<T> implements AddNext<T>, Build<T> {

private static class Node<Item> {
private final int index;
private final Item item;
private Node<Item> next;

private Node(int idx, Item nestedItem, Node<Item> nextNode) {
index = idx;
item = nestedItem;
next = nextNode;
}

private static <V> Node<V> firstNodeOf(V item) {
return new Node<>(0, item, null);
}

private static <V> Node<V> nextNodeOf(V item, Node<V> nextNode) {
return new Node<>(nextNode.index + 1, item, nextNode);
}
}

@Override
Node<T> oldFirst = instance.first;

if (instance.isEmpty())
instance.first = Node.firstNodeOf(item);
else
instance.first = Node.nextNodeOf(item, oldFirst);
instance.count++;

return this;
}

@Override
public Build<T> defineCycleOrBuild() {
return this;
}

@Override
public Build<T> connectLastTo(int index) {
if (instance.isEmpty()) throw new IllegalStateException("Stack underflow");
Node<T> node = findAt(index);
Node<T> last = findLast();
last.next = node;
return this;
}

@Override
public CyclicLinkedList<T> build() {
return instance;
}

private Node<T> findAt(int index) {
for (Node<T> x = instance.first; x != null; x = x.next)
if (x.index == index) return x;
throw new IllegalStateException(String.format("Cannot find node at index %s", index));
}

private Node<T> findLast() {
for (Node<T> x = instance.first; x != null; x = x.next)
if (x.next == null) return x;
throw new IllegalStateException("Cannot find last node - malformed linked list");
}
}


And here is the test suite:

public class CyclicLinkedListTest {

@Test
public void testListNoCycle() {
CyclicLinkedList<Integer> list = listBuilder.defineCycleOrBuild().build();
assertEquals(Optional.empty(), list.firstNodeInCycle());
}

@Test
public void testListCycleAtBeginning() {

CyclicLinkedList<Integer> list = listBuilder
.defineCycleOrBuild()
.connectLastTo(4) // node index
.build();

assertEquals(Optional.of(10), list.firstNodeInCycle());
}

@Test
public void testListCycleInMiddle() {

CyclicLinkedList<Integer> list = listBuilder
.defineCycleOrBuild()
.connectLastTo(2) // node index
.build();

assertEquals(Optional.of(30), list.firstNodeInCycle());
}

@Test
public void testListCycleAtEnd() {

CyclicLinkedList<Integer> list = listBuilder
.defineCycleOrBuild()
.connectLastTo(0) // node index
.build();

assertEquals(Optional.of(50), list.firstNodeInCycle());
}

}


    while (true) {
if (fast == null) return Optional.empty(); // if fast reaches end, no cycle
fast = fast.next; // advance fast one more step
if (fast == null) return Optional.empty(); // again check if fast reached end - if it does, no cycle
fast = fast.next; // advance both one step
slow = slow.next;
if (fast.index == slow.index) { // if fast and slow are equal, that can only mean fast has reached slow from behind, thus proving cycle
slow = first;
while (true) { // find the starting point of the cycle
if (fast.index == slow.index) return Optional.of(slow.item);
slow = slow.next;
fast = fast.next;
}
}
}


I'd write this differently. Consider

    do {
if (fast == null || fast.next == null) {
// if fast reaches end, no cycle
return Optional.empty();
}

// advance fast two steps and slow one step
fast = fast.next.next;
slow = slow.next;
} while (fast.index != slow.index);

// if fast and slow are equal,
// that can only mean fast has reached slow from behind, thus proving cycle
slow = first;
// find the starting point of the cycle
while (fast.index != slow.index) {
slow = slow.next;
fast = fast.next;
}

return Optional.of(slow.item);


This reduces the number of branches by moving the condition into the looping check.

This reduces the indent by separating testing for a cycle from finding the cycle.

I prefer checking both exit conditions in the same if.

I prefer to always use the block version of the if.

There is an error here. We do fast.index before we check if fast is null. This is in both this code and your original. I believe that your code relies on there being an odd number of elements in the list. You only test with five elements. I expect that it would fail on an even number of elements, e.g. two. Haven't tried it though.

• Excellent suggestions and nicely spotted bug. I've also rewritten the code as you had suggested and added the fast null check on while loop exit - it is arguably a little bit harder to read but it feels more elegant; can't say which version is the more perfomant one, probably yours due to reduction in cyclomatic complexity. I especially like how we perform the check and search in two different stages. Aside from a full stochastic test harness, can you suggest some alternative testing strategy that may be useful? Dec 23, 2016 at 6:04