Please refer this post for linked list basics and all other operations on linked lists.
Loops in linked list can be detected by inserting dummy nodes after every node, so if we find dummy node after a node already, that says that list has a loop. The diagram below explains this. This method takes O(n) time and O(n) additional space.
Loops in linked list can also be detected by running two loops paralally, one loop traverse list by one node, another loop traverse list by skipping a node while going to next node. this way they meet at some point of time, if the list has a loop. The diagram below explains this. This method takes O(n) time in best case.
program for finding loop by traversing with two pointers… this program takes input as linked list, returns a node(where a loop starts), or returns NULL if we could not find a loop…
Node *detectloop(Node *list)
{
Node *n1, *n2;
//prev indicates loop started at this point
Node *prev=NULL;
for(n1=list, n2=list; (n1!=NULL) && (n2!=NULL); )
{
if (prev && (n1 == n2))
{
return prev;
}
prev = n1;
n1=n1->next;
n2=n2->next;
if (n2)
{
n2=n2->next;
}
}
}
comments?
Data Structures Blog 
Can we not just run a loop checking for where the next is pointing?
so long as it finds a new address there is no loop.
how can we say the next is address is new address?, again we need to look back at our old traversed nodes to find out whether it is a new address or old address, for doing this it will cost us O(n2).
ohh okay, but i have a small question,
the address that a pointer shows, is it the true location or just a relative indicator?
As the nodes will be malloc’ed, so we are going to get memory from heap, so it is a true location, all nodes will have different addresses (and there is no way they are related)…
I think we need to increment the pointer to the node ‘n2’ one more time in the for loop of the algorithm to find the loop in the list.With the present implemention, for loop in the algorithm will never terminate on trying to detect the loop,when a loop is present(because no pointer will be equal to NULL on incrementing because of the loop).Anyways, to fix the problem I feel we must do the following correction in the for loop:
if(n2 && (n2->next)){
n2 = ((n2->next)->next);
}
else{
// no loop found
return;
}
pratap, there is no issue in the algorithm, it terminates when list has loop because n1 == n2, and that is the start of the loop so it returns from that location. In fact the only difference from your mentioned piece of code and the listed code is listed code moves 2nd pinter at +1, your code moves 2nd pointer at +2 speed.
o(n) doesnt look good, specially because its modifying the original list, i’d rather hash the addresses into an N element hash list with open addressing, it uses less space too(no links sweetie). and is easy to keep track of(no linking either sunshine), just a random thought thou.
Please suggest how does this implementations looks like…
public Node CheckAndFixIfCycle(){
Node nodeFirstCounter = nodeHeader.next;
Node nodeSecondCounter = nodeHeader.next;
Node nodePrevFirstCounter = null;
Node nodeToFix = null;
while(nodeSecondCounter.next != null){
nodePrevFirstCounter = nodeFirstCounter;
nodeFirstCounter = nodeFirstCounter.next;
nodeSecondCounter = nodeSecondCounter.next.next;
if(nodeSecondCounter == nodeFirstCounter){
Console.WriteLine(“Cyclic List….”);
nodeToFix = nodePrevFirstCounter;
//always prev first pointer would be the culprit/node to be fixed and if we nullify that we have fixed the List
nodeToFix.next = null;
break;
}
}
return nodeToFix;
}