looped linked list - head ptr only

[longliz]

hi i forgot to mention that in the linked list - only a head pointer is supplied to a linked list which is arbitrarily long. and the aim is to find out if it is looped ,in a more efficient manner - rather than by checking each pointer againsta all the other pointers which would be a quadratic function.

 

[Zyrenthian]

I would get a head pointer and loop

while(cur != head && cur)
cur = cur->next

that is just a small sample. There will be some other steps you need to do.

Matt

 

[mingis]

Matt, in case of looped list your sample will never stop

 

[Zyrenthian]

If the list is looped cur != head will stop it, in the case of a regular linked list, the && cur will stop it. Looks good to me.

Matt

 

[Zyrenthian]

Re-reading the post, i see that the quadradic aproach i took was not the way to go. Guess my earlier post was not good. Well, given only the head... is it possible to know how many elements are in the list? If not then I suggest the sneaky approach. The list should know how to handle a delete. Get head->next and head->next->next. Set head->next = to null and never lose the pointer to head->next->next. Then just do a delete on head->next and see if head and head->next are equal. Then just restore the list. Let me know if this approach is possible.

matt

 

[longliz]

matt, the list may have a loop anywhere, ie from ANY intermediate element to ANY other previous element. the list may be of any length. i thought i had a solution to it but that too turned out to be quadratic (hashing).