Yahoo

  www.yahoo.com
Work in HR? Unlock Free Profile

Yahoo Software Engineer Interview Question

"How to find out if a linked list has a loop?"
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 530 Yahoo Interview Reviews

Answers & Comments

0
of 0
votes

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
of 0
votes

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

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

Tags are like keywords that help categorize interview questions that have something in common.