Loop in a linked list - C

In article <fdfddh$obh$1@news4.fe.internet.bosch.com>,
Rohit kumar Chandel <rohitkumar.chandel@in.bosch.com> wrote:
>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



--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

In article <fdfddh$obh$1@news4.fe.internet.bosch.com>,
Rohit kumar Chandel <rohitkumar.chandel@in.bosch.com> wrote:
>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 ;-)

--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers