Write an algorithm to find loop in a linked list?
Start with two pointers (ptr1 and ptr2), both pointing to the first node of the given list. Now traverse the linked list with ptr1 two nodes forward and ptr2 one node forward. Stop when ptr1 reaches to end of linked list or both the pointers pointing to same node i.e. ptr1 = ptr2.
1. Ptr1 = ptr2 then linked list contain loop.
2. If ptr1 reached end of the list that means list doesn’t contains loop.
There can be other solution for this problem if we are allowed to change structure of list node. We can add marker field to each node and start traversing the list from beginning and as soon as we visit a node, we’ll mark the field as ‘visited’. If we find any node with marker field as ‘visited’ that means list contains loop.
What is a dangling pointer?
A dangling pointer is a pointer to memory that is no longer allocated. The pointer still points to the memory which earlier was allocated for the data. The data is deleted and the memory may now be used with some other purpose.
{
char *danglingPointer = NULL;
/* … */
{
char localChar;
danglingPointer = &localChar;
}
/* Memory was allocated to danglingPointer in the block. */
/* As soon as program is out of block dandlingPointer points to Memory, */
/* which is free for other use.*/
}