kundanthebest

 Profile Answers by kundanthebest 

• Mar 3rd, 2008

 

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.

// Best solution 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; }