Loop in a linked list

[Rohit kumar Chandel]

How to find whether there is a loop in a linked list. suppose I have a
linked list in the shape of numeral 9(next pointer of last node points to
somewhere in the middle of list instead of pointing to NULL)

 

[Richard Tobin]

How to find whether there is a loop in a linked list. suppose I have a
linked list in the shape of numeral 9(next pointer of last node points to
somewhere in the middle of list instead of pointing to NULL)

A traditional technique is to have two pointers go along the list, one
twice as fast as the other. If there's a loop, they will eventually
be equal. If there isn't, the fast one will run off the end.

-- Richard

 

[Walter Roberson]

How to find whether there is a loop in a linked list. suppose I have a
linked list in the shape of numeral 9(next pointer of last node points to
somewhere in the middle of list instead of pointing to NULL)

Have a 'mark' field in each node. Start at the first member of
the list and set the mark field, and then traverse to the children.
If you encounter a node which already has the 'mark' field set,
then you have a loop in the list.
How to clear all the marks is left as an exercise for the reader ;-)