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;
}
