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

- 07-01-2009transgalactic2how to use the same principle..
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

?? - 07-01-2009bithub
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. - 07-01-2009MK27
- 07-01-2009transgalactic2
- 07-01-2009bithub
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.

- 07-01-2009transgalactic2
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 - 07-01-2009MK27
- 07-01-2009bithubQuote:

Why would the turtle ever equal the rabbit?

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

- 07-01-2009MK27
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.

Code:`--------`

.|

-.-|

--.--|

|--.----

-|--.

---|-.

-----|.

-------X

- 07-01-2009bithubQuote:

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.

- 07-01-2009itCbitC