how to check circular link list

[csaawariya]

hi..i am having problem in writing a function which returns a boolean value if the linked list is circular or not...the linked list is singly...moreover the circular means here not simply last node next is first node but linked list can be circular from any node to any node...
i am giving below the basic syntax that i have implemeted but i am not getting how can i implement using two pointers...the parameter to the function is the head of the linked list and remember you dont have to use here the value of the node...

bool samplefunction(linkedlist header)
{
linkedlist p1,p2;

return bool;
}

thanks in advance...

[Murtan]

Not much on the effort part there...

The algorithm will be something like:

• Start at the head node
• While there is a next node
• If the next node is the head node, the list is circular
• If we got to the end because there was no next node, the list is not

[csaawariya]

hi yes you are right to some extent but i already specified the linked list is not circular from last node to first node but inspite it can be circular from any node to any node...hope you get the logic...

[Murtan]

If it is ever circular, other than tail to head, you have a broken list, there will be nodes you can't get to.

The only test I come up with is to run through the list looking for an end or run through looking for a 'duplicate' node.

The first case could be fairly simple if you know how many items should be on the list (or a maximum number of items that could be on the list). Traverse either the known count or the maximum count looking for an end, if you don't find one, you're probably looping.

For the second case, you need a way to 'record' all the nodes you have seen before and as you traverse to a 'new' node, you make sure that it is not on the list of nodes you have recorded. If you have seen it before, you have an improperly circular list.

[StuXYZ]

Acutally this is a "classic" interview question. (Which I have never used/heard).

You start with two pointers, you advance one two time, and the other one time. If you go past the end, you set it to the first item.
If the two pointers match at any time before the last item of the list
then you have a loop.

The special case if a cyclic loop which is true if the two pointers match on the last item BUT the first pointer hasn't had to be jumped to the start of the data.