Find loop in linked list and remove the loop

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
}

One Thought on “Find loop in linked list and remove the loop

  1. 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;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation