Checking the circularity of a singly linked list

[AnotherBuddy]

Can anyone tell me the logic for:
Checking the circularity of a singly linked list? The logic should not depend on the length of the list. if the list is partially circular (eg last node pointing to 4th node), the logic should not fail and logic should have a complexity of constant.

Thanks,
buddy

[gstercken]

Checking the circularity of a singly linked list? The logic should not depend on the length of the list. if the list is partially circular (eg last node pointing to 4th node), the logic should not fail and logic should have a complexity of constant.

It should be obvious that an existing linked list can't be checked in constant time. However, you could maintain a flag in each node which indicates whether the node is already referenced, this would allow to check for circular references upon insertion. But anyway, this is a rather academic discussion (which is not what this forum is for). For any practical purpose, use std::list or CList: Since the linking logic is an implementation detail of those containers, the interface won't even allow you to create circular references. So I wonder why you want to reinvent the wheel and implement a linked list yourself, instead of using the existing container classes.