CareerCup

Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4.)Move both pointers at the same pace, they will meet at loop starting node.

use two pointers....head.next,head.next.next

My soln will work with O(n2) complexity can anyone come up with some better way ??

Make another copy of the linkedlist.

modify the link traversal in the following way

struct node *current=first;
while(current->next!=NULL){
  current=current->next;
  current->data+=1;
 }

now start traversing the original and the copied linked list simultaneously and compare the data of the nodes of each node, which ever node has the difference=2 , is the start of the cycle

Complexity : Time: O(n)
Space: O(n)

count the total number of nodes in the loop. this we can find out using tortoise and hare algorithm. after that find out the total number of nodes in the link list. then the node at which the loop is starting will be : total number of nodes in the link list - total number of nodes in the loop + 1.

Use a HashMap. Start at head. Store the address (or hash code) of the code you are at currently in this HashMap. When you come to a node, check to see if the object is present in the HashMap. The first hit is where the cycle starts. It is O(n) but requires extra storage.

What about the collision in the hash table?? Does it not create a false positive??

N - number of nodes.
M - number of nodes in the cycle.

Then, the address of where the cycle start is the (N - M + 1) node.

It can be done in O(n) .... Two separate loops.
In one loop check where the fast pointer meets slow pointer.O(n)
After that keep slow pointer at that position and make fast pointer point to head.
Keep advancing both pointers one place at a time.O(n)
The place where they meet now is the start of loop.

@ Geeks... isnt it shld be (k+1)th node in 3rd step....

1).Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4.)Move both pointers at the same pace, they will meet at loop starting node.

traverse hole array and hash the addresses of the node
if address already contained by hash table therefore loop start with this node ...

1. mark each node you have traversed.
2. the first "marked" node you encounter is the answer.