Loop Detection

problem

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

how to solve

If I can use extra space, I can solve this very easily. I can justly use a hash table to detect if the element is appeared or not.

Next, I want to consider this problem without using that data structure. I took the following steps.

• Create two pointers, FastPointer and SlowPointer.
• Move fastPointer at a rate of 2 steps and SlowPointer at a rate of 1 step.
• When they collide, move SlowPointer to LinkedListHead. Keep FastPointer where it is.
• Move Slow Pointer and FastPointer at a rate of one step. Return the new collision point

code1

without using extra space.

code2(with using map)

with using hash map.