Finding a loop in a singly linked list

There are three "decent" solutions for it

1. Pass through the list, use a hashtable to store the addresses of the visited nodes, if 2 nodes hash to same key, there's a loop.

function boolean hasLoop(Node startNode){
  HashSet nodesSeen = new HashSet();
  Node currentNode = startNode;
  do {
    if (nodesSeen.contains(currentNode)) return true;
    nodesSeen.add(currentNode);
  } while (currentNode = currentNode.next());
  return false;
}

2. Floyd's Cycle-Finding Algorithm

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Alternately, in C

p=q=head;
do{
p=p->next->next;
q=q->next;
}while p!=q or p!=null;
if p==q
loop exists
else
no loop

To find the smallest index where the cycle starts:

// To find the smallest index where the cycle starts
// P is set from last algorithm
int index=0;
q=0;
while p!=q{
     p=p->next;
     q=q->next;
     index ++;
}
return index;

To find cycle length

// P & Q  is set from last algorithm
int len=0;
while p!=q{
     p=p->next;     
     len ++;
}
return len;

See reasoning for len, index functions at wiki


3. Brent' Algorithm

power=len=1;
q=head;
p=head->next;

while p!=q {
 if (power==len){
  p=q;
  power*=2 , len=0;
 }
 p=p->next; len++;
 if(p==NULL) return (no cycle);
}
return (cycle), len;

For finding Index

i=index=0;
p=q=head;
while(i++<len)
 p=p->next;

while p!=q {
  q=q->next;
  p=p->next;
  index++;
}
return index;

Reference:
http://ostermiller.org/find_loop_singly_linked_list.html
wiki