Interview Question

Software Engineer Interview

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

Answer

Interview Answer

2 Answers

0

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.

Anonymous on Nov 6, 2013
0

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;

}

}

Soumya on Nov 7, 2013

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up