Interview Question


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


Interview Answer

2 Answers


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

boolean hasLoopInList(Node first){ if(first == null){ return false; } Node slow,first ; slow = first = first ; While(true){ slow = ; if( !=null){ fast =; } 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.