To remove the loop, we need to find the node at which the loop begins.
Detection is easy by using fast and normal pointers (referred to as FP and NP from now on) to traverse such that the fast pointer traverses 2 nodes while normal pointer moves 1 node at a time. If they meet, then there is a loop. [C code]
To find the loop length, move FP and NP once again till they meet.
If loop is of length k, FP and NP will meet again after NP has moved k/2 nodes and FP has moved k nodes.
To find the loop beginning, take two pointers from the list beginning but separated by k nodes. At that time, the first pointer is N-k node from the loop beginning and second pointer is N-k from the loop end. So if we move them till they meet, then they will meet after N-k nodes i.e. at the loop beginning.
void removeLoop(node loopNode, node head)
{
node ptr1 = loopNode;
node ptr2 = loopNode;
int looplen = 1;
// count the number of nodes in loop
while(ptr1->next != ptr2)
{
ptr1 = ptr1->next;
looplen++;
}
ptr1 = head;
ptr2 = head;
for(i=0; i < looplen; i++)
{
ptr2 = ptr2->next;
}
while(ptr2->next != ptr1->next)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
ptr2->next = NULL; // breaking the loop
}
C-program to create, detect and remove the loop in a linked list;
void
ll_loop_detect(llnode_t **head)
{
llnode_t *slow, *fast;
int loop_node_key;
/* Create loop in the linked list */
do {
printf("Enter the key node to create loop:");
scanf("%d", &loop_node_key);
for (slow = *head;
slow && (slow->key != loop_node_key);
slow = slow->next);
if (!slow || (slow == *head)) {
slow = NULL;
printf("Not able to create loop");
} else {
slow->next = *head;
}
} while(slow == NULL);
/* Detect the loop in the linked list */
for (slow = fast = *head;
slow && fast;
slow = slow->next, fast = fast->next->next) {
if (slow == fast) {
printf("Loop is detected and loop node keys are slow->key: %d fast->key: %dn",
slow->key, fast->key);
break;
}
}
/* Remove the loop */
for (slow = *head;
(slow->next != fast);
slow = slow->next);
slow->next = NULL;
}
This is not correct. slow jump and fast jump can point to any two nodes in the loop. But how do you know its the node creating the loop. As per you above program I needn’t have another loop to remove in the earlier loop itself I could have additional variable capturing slow_prev and solve the purpose. But your solution isn’t right.
Its valid if both slow and fast are moved by 1 at a time..