1
\$\begingroup\$

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);
}
\$\endgroup\$
2
\$\begingroup\$
    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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – quantum Dec 23 '16 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.