June 16th, 2003, 01:16 AM
In a linked list, I have the last node pointing somewhere to the
middle of the linked list. How should I find out where the circular link appears?
June 16th, 2003, 12:22 PM
i'm guessing you should walk through it and load each item into a new list - if it doesn't already exist in the new list. the first item you get pointing to an item already in the new list is the then last item.
June 25th, 2003, 06:06 AM
to chk whether is a link is circular, use 2 pointers, and traverse ,, say p and q
for p , increment p = p->next
and q q=q->next->next
(take care of error checks )
eventually they'll have to meet.. if its circular
Alternatively u can have an additional flag for every list item: visited or not ... once the flag is set true.. i.e visited and u try visiting it again, u know its circular...
June 25th, 2003, 06:26 AM
Hello no expert thanks...
but my friend had already found the logic in the book "art of programming".
Thanks for taking a effort to mail me.
you seem to be tamilian right?
June 25th, 2003, 06:31 AM
what is the solution that ur friend has got ?
Cud u plz post that also for the benefits of "non experts" in this forum..
oh yup, naan oru tamizacchi
June 25th, 2003, 06:34 AM
Hello no expert,
it's the same logic use 2 iterators and at one point they would meet.
I think your flag idea is innovative.
June 25th, 2003, 06:39 AM
FYI monty, the flag idea is one of the "bad ideas" to solve the pblm..
to find a solution , one of the last things that you must resort to
is change the data structure itself... u may be asking why?
say suppose u have an additional flag, it cud be a char/int/bit field
dat wud mean increasing the space complexity. The last thing u must do is to increase the space complexity..
the flag idea is O(n) (i hope u are comfy with such notations) but requires more space,
the iterating way using 2 pointers is the best way to do it. acc 2 me..
June 25th, 2003, 06:47 AM
Hello no expert,
I agree with you about the flag idea.
But instead of thinking logically,and in lateral context i think it's a good idea.
you seem to be intelligent tamilachi!