Find and Remove loop in a Linked List

Find and Remove loop in a Linked List

Question:

Find and Remove loop in a singly linked list.

Logic:

  • Create two pointer slow and fast both are pointing to head.
  • Move slow pointer one step and fast pointer two steps forward.
  • Both slow and fast pointer will meet one point, if loop exists
  • Assign head value to slow, then move both slow and fast one step forward
  • There meeting point is the loop’s starting point and then point fast->next = NULL
  • In some case both head and fast will be same, need to move fast pointer till the starting of loop
  • Print the result of removed loop in linked list

Explanation:

Find Loop:

find loop

Remove loop:

 

Program:

#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
	int value;
	struct Node *next;
}Node;

/*print the elements*/
void printList(Node *head)
{
	while(head)
	{
		printf("%d ",head->value);
		head = head->next;
	}
}

/*function to create a new node into the list*/
Node* addNode(int value)
{
	Node *temp = (Node*)malloc(sizeof(Node));
	temp->value = value;
	temp->next = NULL;
	return temp;
}

/*find and remove loop in linked list*/
void findAndRemoveLoop(Node* head)
{
	Node *slow = head;
	Node *fast = head;

	while(fast->next)
	{

		fast = fast->next->next;
		slow = slow->next;	
		/*found the loop*/
		if(slow == fast)
			break;

	}

	if(slow == fast)
	{
		slow = head;

		/*Both head and fast pointing to same node*/
		if(slow == fast)
		{
			/*traverse to loop starting point*/ 
			while(fast->next != slow)
				fast = fast->next;
		}
		else
		{
			/*traverse to loop starting point*/
			while(fast->next)
       			{
               		
               			if(fast->next == slow->next)
					break;

               			fast = fast->next;
               			slow = slow->next;
       			}
		}
		fast->next = NULL;
	}
}

void main()
{
	Node *head = addNode(1);
	head->next = addNode(2);
	head->next ->next = addNode(3);
	head->next->next->next = addNode(4);
	head->next->next->next->next = addNode(5);
	head->next->next->next->next->next = addNode(6);
	head->next->next->next->next->next->next = addNode(7);

	/*Creating loop pointing to 3rd node*/
	head->next->next->next->next->next->next->next = head->next->next;

	findAndRemoveLoop(head);

	printList(head);
}


You might also like:

Merge Two Sorted List | Microsoft | Samsung

Linked List

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Vignesh

A Computer Science graduate who likes to make things simpler. When he’s not working, you can find him surfing the web, learning facts, tricks and life hacks. He also enjoys movies in his leisure time.
0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x