Linked list.

Hello,
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?


Monty

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.

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...
enna purinchida?

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?

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

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.

thanks tamilachi

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..

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!