Yahoo
3.4 of 5 1,679 reviews
www.yahoo.com Sunnyvale, CA 5000+ Employees

Yahoo Software Engineer Interview Question

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

Part of a Software Engineer Interview Review - one of 523 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 Flag Response
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 Flag Response

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.

Glassdoor is your free inside look at Yahoo interview questions and advice. All interview reviews posted anonymously by Yahoo employees and interview candidates.