How to find out if a linked list has a loop?

Question

Anonymous · Accepted Answer

The hare and tortoise algorithm can be used. Start at node X and X+1. Have 2 pointers. One goes to next() and another goes to next().next() [twice as fast]. At some point, both pointers will be on same node Y. If you reach a null for second pointer, at any point, then there is no cycle.

Soumya · Answer

boolean hasLoopInList(Node first){
  if(first == null){
   return false; 
}

Node slow,first ; 

  slow = first = first ;

While(true){

  slow = slow.next ; 
if(fast.next !=null){
  fast = fast.next.next;
}

  if(first ==null || slow ==null) return false;

 if(slow == fast) // if the two ever meet...we must have a loop.
            return true; 


}

}

Yahoo

Yahoo Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches