Delete loop from linked list,made easy with 9 Pictures

By | February 17, 2017

Each node will point to next node in the loop.it can form loop if it makes pointing to same node previously.Let’s go by some example.

Problem can be solved by using the below technique:

We have to take two pointers say ( slow Pointer ) and fast pointer ( 2 times of slow pointer ).first we will find out the loop by moving the slow pointer from head by one and head pointer move by 2 times of lenth.They will meet at the one point.if they meet we call there is a loop.

Delete loop from linked list made easy

                                                                            Delete loop from linked list made easy

Once,we find out the the loop,head pointer and slow pointer will point at one node.Now,we have to take out slow pointer at the head place  move by once.Head pointer from meeting point at once.we need to check,whether they are meeting at one point or not.

if they meet again,this time we need to make Head pointer to NULL for breaking the loop.Because head->next is making the loop here.

I have tried max to put this in diagram’s as below.give a try in understanding the same.

Detecting loop in Linked List 1

 

Detecting loop in Linked List 2

 

 

Here is the Complete Code,which i have used for compilation and execution.

#include <bits/stdc++.h>
#include <string.h>
using namespace std;
// Structure of node.It contains two elements.one is string.
// Second one is Pointer to Node

struct node
{
 int data;
 struct node* next;
};

/* Function to create a new node with given data */
node* newNode(int data)
{
 node *new_node = new node;
 new_node->data = data;
 new_node->next = NULL;
 return new_node;
}


node* GenerateLinkedList(int n)
{
 int data;
 int i;
 
 struct node *temp;
 struct node *headtemp;
 struct node *head;
 struct node *newlycreatednode;

 printf("Enter the data of first node:-\n\n");
 cin >> data;
 cout << endl << endl;
 
 head = newNode(data);
 temp = head;

 
 //this loop will be executed,if it is more than 2 nodes. 
 for(i=2; i<=n; i++)
 {
 printf("Enter the data of %d node:-\n\n",i);
 cin >> data;
 cout << endl << endl;
 newlycreatednode = newNode(data);
 newlycreatednode->next = NULL;
 
 temp->next = newlycreatednode; 
 temp = temp->next;
 } 
 printf("Linked List Created with nodes - %d successfully \n\n",n);
 
 return head;//return reference to head element of the linked list.
}

void displayLinkedList(node *head)
{
 struct node *temp;
 
 if(head == NULL)
 {
 printf("I am sorry Bro,LinkedList is empty.\n\n");
 }
 else
 {
 temp = head;
 printf("Displaying linked List.\n\n");
 while(temp != NULL)
 {
 cout<<temp->data<<"=====>";
 temp = temp->next; 
 }
 
 printf("END\n\n"); 
 }
} 


void removeLoopFromLinkedList(node* headPointer)
{
 node *tempHeadPointer = headPointer;

 /*Now Lets take two pointers one slow and one is Head Pointer */
 //start fast pointer ahead of one step.
 node *slowPointer = headPointer;
 node *fastPointer = headPointer->next;
 
 // Search for loop using slow and fast pointers
 // Basically,this while loop will exit , if there is a loop
 // we are moving slowPointer by one time.
 // we are moving FastPointer by Two times.
 // if they meet at one point ,means there is a loop
 // As per our test data,it will meet at 30
 // So,it will exit at 30,both fastPointer,SlowPointer will point at 30
 while (fastPointer && fastPointer->next)
 {
 if (slowPointer == fastPointer)
 break;
 slowPointer = slowPointer->next;
 fastPointer = fastPointer->next->next;
 }
 
 //If ther is a loop,we will enter into this below If Condition
 //We are making slowPointer at Head Position.
 //But Fast Pointer will be at looping point only
 //that is Fast Pointer will be at 30 only
 //Now,move FastPointer and slowPointer by one time
 //Move them by one untill they meet.
 //If they meet,now take out fastPointer->next to NULL
 //Why fastPointer only ?
 // Because we have started slowPointer at Head,Obviously
 // fast Pointer is the lead runner compared to slowPointer 

 
 if (slowPointer == fastPointer)
 {
 slowPointer = headPointer;
 while (slowPointer != fastPointer->next)
 {
 slowPointer = slowPointer->next;
 fastPointer = fastPointer->next;
 }
 
 //we are making fastPointer to NULL,so that we are breaking the loop.
 
 fastPointer->next = NULL; 
 }
}

//Main program
int main()
{
 
 printf("Creating Linked list \n");
 /*Create head element */
 node *head = newNode(10);
 /*Add Second element 10->20 */
 head->next = newNode(20);
 /*Add Third element 10->20->30*/
 head->next->next = newNode(30);
 /*Add Fourth element 10->20->30->40*/
 head->next->next->next = newNode(40);
 
 //Display created linked list.
 printf("Displaying LinkedList \n");
 displayLinkedList(head);
 printf("Creating loop in the LinkedList \n");
 printf("10=====>20=====>30=====>40=====>30 LOOOOOP \n");

/* 
 10->20->30->40
 ^ |
 | | 
 | |
 |----| 
 I am just creating Loop by making Loop from 40 to 30 */
 
 
 /* Below Statement will make loop from 40 to 30 */
 head->next->next->next->next = head->next->next;
 
 printf("Removing the loop in the linked list \n");
 removeLoopFromLinkedList(head);
 
 printf("Existing Linked List Elements After Deletion of Loop Element \n\n");
 
 //Display created linked list.
 displayLinkedList(head);
 
 return 0;
}

Below Screenshot,i have taken after compilation and Execution.you can follow the same.

Compilation and Execution of “delete loop from linkedlist”

Hope you have learned the Logic behind the deletion of loop from linked list.

The following two tabs change content below.

SRINIVAS DARIPELLI

Myself SRINIVAS DARIPELLI. I have 15+ Years of Experience in Programming worked on multiple technologies.Apart from it,I am a blogger, writer, editor, artist and dad 🙂 .I believe in reality.I love to share the Helpful things around the Technology. Feel free to connect with me

Leave a Reply