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

## No comments:

Post a Comment