circular singly linked list problem

[zapataboy]

hi all ,
this problem was given to me to solve.

given a pointer to a node in a singly linked list how do u find out whether the list is circular or not?
any solutions other than traversing the whole list.
thanks
sayan

[hspc]

you can save the adresses of the first and last nodes in the list as class members, and compere them.

[yiannakop]

I think that the first and last nodes are not the same nodes in a circular list. What happens is that the last node "points" to the first node of the list. In normal lists (not circular) the last node points to NULL.

[hspc]

Originally posted by yiannakop
I think that the first and last nodes are not the same nodes in a circular list. What happens is that the last node "points" to the first node of the list.

since it's circuler .. this makes no difference :p

[Luchin_plusplus]

If you don't know where the last pointer on (last.next) points to, the only way is to traverse the whole list- This is by definition.

If you know the last pointer points to a specific node (which is assumed to be either the header or the first node of the list), you spend less time simply traversing from that node. You expect to reach your current node in less time that you would spend going forwards to reach the end of the list and then go back to the begginning.

But, as I said, the only way to know for sure, is to iterate through it. No matter what is the implementation (singled, doubled; with extra nodes for the beg or end, etc), if you reach your node _twice_ fron anywhere (once from itself), the list _is_ circular.

[N0Em0t10n]

I think following steps will solve your problem.
1 ] ptr1 = current given prointer;
2 ] ptr2 = current given pointer;
3]
do
{
pt1 = ptr1 -> next;
ptr2 = ptr2 -> next-> next;
}
while (ptr2 != NULL && ptr1 != ptr2)

4] If you find ptr2 as a NULL then linked list is not circular
and if you find ptr1== ptr2 then linked list has loop.

[ka3ak]

I think following steps will solve your problem.
1 ] ptr1 = current given prointer;
2 ] ptr2 = current given pointer;
3]
do
{
pt1 = ptr1 -> next;
ptr2 = ptr2 -> next-> next;
}
while (ptr2 != NULL && ptr1 != ptr2)

4] If you find ptr2 as a NULL then linked list is not circular
and if you find ptr1== ptr2 then linked list has loop.

will this still work if the loop is of size 3 nodes?

[logan]

Use the two pointer approach.

Rough code:


bool ContainsLoop (Node *pNode)
{
Node *pSlowptr = pNode;
Node *pFastptr = pNode->pNext;
while (pFastptr != NULL || pSlowptr != NULL)
{
if (pSlowptr == pFastptr)
return true;

pSlowptr = pSlowptr->pNext;
if (pFastptr->pNext)
pFastptr = pFastptr->pNext->pNext;
else
pFastptr = NULL;
}
return false;


Hope it helps.

[ka3ak]

will this still work if the loop is of size 3 nodes?

my bad, misread the question.

[code_carnage]

Is there any proof that two pointer approach will work..???

I mean any mathematical proof or something...

[Culperat]

Is a proof that neccessary? I mean, all its doing is having one pointer go through the list one at a time, the second pointer will go through the list at double the rate.

If the list isn't circular, the second pointer will be null. Answer 1 given, not circular.
Else the second point will loop through the list once or twice dependant on the amount of elements in the list. Twice if n is even, once if n is odd.
(Note: O(n), because this algorithm takes n steps.)

The two are inevitable to meet based on taking it as factors, they will come to a common meeting point.


Another way to approach this is save the starting point, run through the entire list untill null or the starting point is found. Based on which one is the result you would know if its circular or not. It would still be O(n) so there wouldn't be any benefit, just another option.