how to use the same principle..

[transgalactic2]

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

[bithub]

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.

[MK27]

a list of visited nodes

that could be an array of node pointers.

[transgalactic2]

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.

i need to use only something similar to the rabbit turtle
algorithm

[bithub]

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.

[transgalactic2]

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

[MK27]

Keep doing this until either the rabbit equals NULL, or the turtle equals the rabbit.

Why would the turtle ever equal the rabbit?

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

You can't.

[bithub]

Why would the turtle ever equal the rabbit?

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.

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

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.

[MK27]

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.

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.

--------
.|
-.-|
--.--|
|--.----
-|--.
---|-.
-----|.
-------X

Here's eight nodes in a circular list where "." is the turtle, "|" is the rabbit and X is both.

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

Yeah, the efficiency should be O(n).

[itCbitC]

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

The turtle-rabbit algorithm for detecting loops in a linked list implementation is an established one.
Did you try to Google it? There are plenty of code examples to help get you started on this quest.