Solution Approach:
Create two pointers ,Fast Pointer and Slow Pointer.
Move Fast Pointer at a rate of 2 and slow pointer at rate of 1.
When they collide ,move slow pointer to linkedlisthead.keep fast pointer where it is.
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;
}