Detect loop in linked list

Question

First, I should mention that I've already checked out and understood the most popular algorithm for detecting whether a linked list has a loop in it or not (talking about this How to detect a loop in a linked list? )

However, I tried implementing my own idea and it seemed to work on my examples - however it failed in execution time on http://leetcode.com/ which made me think that somehow it can enter an infinite loop.

My problem is: I need to know whether my code is correct or it does indeed enter infinite loops in some cases.

This is the definition for singly-linked list.

class ListNode {
   int val;
   ListNode next;
   ListNode(int x) {
       val = x;
       next = null;
   }
}

This is the function:

public boolean hasCycle(ListNode head) {
    //create a list that will contain the elements that have been visited
    List<ListNode> ref = new ArrayList<ListNode>();

    ListNode element = head;
    //add the first element to the list
    ref.add(head);

    boolean contains = false;

    //the special case when the linkedlist is empty
    if(head==null)
        return false;
    while(contains == false){
        if(element.next!=null && !ref.contains(element.next)){
            ref.add(element.next);
            element = element.next;
            contains = false;
        }
        else if (ref.contains(element.next))
            contains = true;
        else if(element.next == null)
            return false;
    }
    return contains;
}

Answer 1

I don't think it's possible for your code to enter an infinite loop. Following the possible control flows of your algorithm:

• If the head is null, return false. The head being null is now an invariant.
• If the head's next node is itself, return false. The head is preemptively added to the collection of visited elements, making this trivial.
• If the current node's next node is non-null and has not been previously visited, add it to the list of visited nodes and continue execution.
• If the current node's next node is non-null but has been previously visited, perform a (now superfluous) check to ensure that the node has definitely been previously visited. At this point we are guaranteed to have a loop within the list, and so we return true.
• If the current node's next node is null, check if any null nodes have been previously visited. This particular branch cannot be reached thanks to our invariant that the head is not null to begin with.
• Perform a (now superfluous) check to see if the current node's next node is null. At this point the current element's next element being null is guaranteed, making it trivial to conclude that by the time the list has been fully traversed no loop has been encountered and that it is safe to return false.

At no point is there a branch that leads to the state of the program not advancing in some way, making it safe to say that having an infinite loop is not a problem.

The real problem with your algorithm looks to be its time complexity. Ensuring that a java.util.ArrayList does not contain a particular value requires fully traversing the list and calling Object#equals on every element, every single time. If you are dead-set against using one of the more traditional cyclic node link checking algorithms like the one you linked, I'd definitely suggest using a java.util.HashSet for something like this instead. It provides very fast lookups by design for whether or not an element is present within it.

Also, if you're in a less contrived situation where there are custom equals and hashCode methods written for nodes, you might have to resort to instead keeping track of nodes via wrapper classes with hashCode and equals methods proxying through System#identityHashCode calls and referential equality checks for the real nodes. Otherwise, the algorithm might determine that a loop exists when one really doesn't.