Thread: Linked list.

    #1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    Chennai
    Posts
    4
    Rep Power
    0

    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
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    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.
  4. #3
  5. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    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?
  6. #4
  7. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    Chennai
    Posts
    4
    Rep Power
    0
    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?
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    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
  10. #6
  11. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    Chennai
    Posts
    4
    Rep Power
    0
    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
  12. #7
  13. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    India
    Posts
    19
    Rep Power
    0
    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..
  14. #8
  15. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2003
    Location
    Chennai
    Posts
    4
    Rep Power
    0
    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!

IMN logo majestic logo threadwatch logo seochat tools logo