How to find whether a linked list has a loop within it.

Question

Anonymous · Accepted Answer

Use 2 pointers, varying the speeds of both. If at sometime they meet each other, that means there exists a loop, else if the reach the end of linked list that means there does not exists a loop.

Tophat · Answer

The previous answer has an indefinite worst case running time, which usually is something you want to avoid.

You can search through the list once adding the pointer addresses to a hashmap.  If ever you reach an address that already exists in the hashmap, then there is a loop.  In the worst case you have to read through the whole list once.  On average, you have to read (n+1)/2 elements.

Anonymous · Answer

While traversing the list from the starting node, you can leave a mark behind, if you encounter a mark in a node, then it's linked. If you reach the end without finding your mark, then it is not linked.

Anonymous · Answer

linked => circular

Harry · Answer

The following blog discussed this problem in details:

http://codercareer.blogspot.com/2012/01/no-29-loop-in-list.html

Goldman Sachs

Goldman Sachs interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?