Floyd's cycle detection algorithm in linked list

Question

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;
private CyclicLinkedList() {}
public static <T> AddNext<T> builder() {
 return new CyclicLinkedList.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> {
 AddNext<T> addNext(T item);
 Build<T> defineCycleOrBuild();
}
public interface Build<T> {
 Build<T> connectLastTo(int index);
 CyclicLinkedList<T> build();
}
private static class Builder<T> implements AddNext<T>, Build<T> {
 private CyclicLinkedList<T> instance = new CyclicLinkedList<>();
 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
 public AddNext<T> addNext(T item) {
 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.AddNext<Integer> listBuilder = standardListBuilder();
 CyclicLinkedList<Integer> list = listBuilder.defineCycleOrBuild().build();
 assertEquals(Optional.empty(), list.firstNodeInCycle());
}
@Test
public void testListCycleAtBeginning() {
 CyclicLinkedList.AddNext<Integer> listBuilder = standardListBuilder();
 CyclicLinkedList<Integer> list = listBuilder
 .defineCycleOrBuild()
 .connectLastTo(4) // node index
 .build();
 assertEquals(Optional.of(10), list.firstNodeInCycle());
}
@Test
public void testListCycleInMiddle() {
 CyclicLinkedList.AddNext<Integer> listBuilder = standardListBuilder();
 CyclicLinkedList<Integer> list = listBuilder
 .defineCycleOrBuild()
 .connectLastTo(2) // node index
 .build();
 assertEquals(Optional.of(30), list.firstNodeInCycle());
}
@Test
public void testListCycleAtEnd() {
 CyclicLinkedList.AddNext<Integer> listBuilder = standardListBuilder();
 CyclicLinkedList<Integer> list = listBuilder
 .defineCycleOrBuild()
 .connectLastTo(0) // node index
 .build();
 assertEquals(Optional.of(50), list.firstNodeInCycle());
}
private static CyclicLinkedList.AddNext<Integer> standardListBuilder() {
 return CyclicLinkedList.<Integer>builder().addNext(50).addNext(40).addNext(30).addNext(20).addNext(10);
}

Answer 1

 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.

• quantum: 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?