Interview Question

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, Sign In or Sign Up.