Loop in a single linked list

[Guptha_S]

Hi,

How to detect a loop in a singly linked list without using any additional pointers (and without deleting any nodes)?

Thanks
Guptha

[sammy]

There are various ways for detect a loop in a singly linked list. But as per your requirement one of the ways of doing this is traverse the list and mark each node as having been seen. If you come to a node that has already been marked, then you know that the list has a loop.There are of course some drawbacks in this method but it would achieve the purpose of detecting the loop.

[Guptha_S]

Thanks for your answer sammy

[sammy]

Gupta hope your query is solved. Let me know if you have any more doubts.I would try my best to resolve the same.

[miolamio]

You should use two pointers and iterate nodes.

Say, first pointer will iterate list from the beginning 1 node per step;
Second will iterate list 2 nodes per step.

If pointers meet each other, that means you're inside the loop.

This won't require any additional data for instances (e.g. flags, indicating previous visits).