i need to find out if a linked list ends with NULL
or go back to one of its members
i was told to ue the turtle rabbit algorithm
which cuts the first half of a given list
i cant understan how the turtle rabbit algorithm is linked to my problem
??
Printable View
i need to find out if a linked list ends with NULL
or go back to one of its members
i was told to ue the turtle rabbit algorithm
which cuts the first half of a given list
i cant understan how the turtle rabbit algorithm is linked to my problem
??
Well, you can always scan through the list and check each node to see if you have wrapped back around to the beginning of the list. If you reach the beginning again, that means the list is circular and therefore doesn't end with NULL.
If the list can wrap back around to any node (not just the head), then you will need to store a list of visited nodes, and check each node you go to to see if you have already visited it. If you have already visited it, then the list does not end with NULL.
that could be an array of node pointers.Quote:
Originally Posted by bithub
i need to use only something similar to the rabbit turtleQuote:
Originally Posted by bithub
algorithm
In that case, create 2 node pointers to iterate through the list. Every iteration through your loop, increment the turtle node pointer to the next node and increment the rabbit pointer two nodes ahead. Keep doing this until either the rabbit equals NULL, or the turtle equals the rabbit.
yes that the turtle rabit algorithm
how to use it in order to find out if the last node
point to NULL
or it points to some other node in the list
Why would the turtle ever equal the rabbit?Quote:
Originally Posted by bithub
You can't.Quote:
Originally Posted by transgalactic2
Because the rabbit is moving faster than the turtle. Therefore, if there is a loop, the rabbit will eventually catch the turtle and they will be on the same node.Quote:
Why would the turtle ever equal the rabbit?
If the rabbit ever hits NULL, then the last node points to NULL. If the rabbit ever lands on the same node as the turtle, then there is a loop.Quote:
how to use it in order to find out if the last node
point to NULL
or it points to some other node in the list
Okay, that makes sense now. I was thinking that the rabbit would be perpetually two steps ahead, but obviously it is 2 then 4 then 6 then 8, etc.Quote:
Originally Posted by bithub
I just did this on paper and noticed that with both odd and even numbered lists the rabbit seems to circle and land on the turtle by the end of the rabbit's second pass, which is also by the end of the turtle's *first* pass.
Here's eight nodes in a circular list where "." is the turtle, "|" is the rabbit and X is both.Code:--------
.|
-.-|
--.--|
|--.----
-|--.
---|-.
-----|.
-------X
Yeah, the efficiency should be O(n).Quote:
I just did this on paper and noticed that with both odd and even numbered lists the rabbit seems to circle and land on the turtle by the end of the rabbit's second pass, which is also by the end of the turtle's *first* pass.
The turtle-rabbit algorithm for detecting loops in a linked list implementation is an established one.Quote:
Originally Posted by transgalactic2
Did you try to Google it? There are plenty of code examples to help get you started on this quest.