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

Solution Approach:

1. Create two pointers ,Fast Pointer and Slow Pointer.
2. Move Fast Pointer at a rate of 2 and slow pointer at rate of 1.
3. When they collide ,move slow pointer to linkedlisthead.keep fast pointer where it is.
4. Move slow pointer and fast pointer at a rate of one step.return the new collision point.

Implementation:

public LinkedListNode FindBeginning(LinkedListNode head)
{
LinkedListNode slow=head;
LinkedListNode fast=head;

while(fast! =null && fast.next !=null)
{
slow =slow.next;
fast=fast.next.next;
if(slow==fast){ // collision
break;
}
}

if(fast == null || fast.next == null)  // no metting point means no loop
return null;

slow=head;
while(slow!=fast)
{
slow=slow.next;
fast=fast.next;
}

}
return fast;


}