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
??
This is a discussion on how to use the same principle.. within the C Programming forums, part of the General Programming Boards category; i need to find out if a linked list ends with NULL or go back to one of its members ...
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.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
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
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
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.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.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.
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
Last edited by MK27; 07-01-2009 at 03:59 PM.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
Yeah, the efficiency should be O(n).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.