Tortoise and hair problem (part 2):

a) Where will this occur in the example above ? Once this has happened, move the tortoise back to the beginning of the list. Start moving the two pointers from their current positions in the list, but both in a step by step fashion: tortoise = tortoise.next hare = hare.next Repeat until the two pointers meet once again : tortoise == hare.

b) Where will this occur in the example above ?

c) Show that whatever is the length x of the initial segment before entering the loop and whatever is the length y of the loop itself, the above process will always find the point connecting the two parts. Provide a formal proof here.

--for a to c, a tutor provided this code http://pastebin.com/VKVLQgAq . i just need some help for D) and E).

d) Combine all this together into an algorithm that breaks an arbitrary list mylist into two sub-lists:

NR = the part of the list from beginning before the connecting point

R = the part of the list closing into a loop starting at the connecting point.

Make sure your algorithm works even if the list does not contain a loop, in which case NR contains the whole list and R is an empty list.

e) Analyse the running time of your algorithm as a function of the number of cells in the list. How much space does your algorithm use as a function of the number of cells in the list.

thanks!