Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Program to Detect and Remove Loop in a Linked List in C++?

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 424
    Comment on it

    // C++ program to detect and remove loop

    using namespace std;
     
    struct Node
    {
        int key;
        struct Node *next;
    };
     
    Node *newNode(int key)   //Function to create a node
    {
        Node *temp = new Node;
        temp->key = key;
        temp->next = NULL;
        return temp;
    }
     
    void printList(Node *head)  //Function to print NodeList
    {
        while (head != NULL)
        {
            cout << head->key << " ";
            head = head->next;
        }
        cout << endl;
    }
     
    void detectAndRemoveLoop(Node *head)     //Detecting and Removing Loop in LinkedList
    {
        Node *slow = head;
        Node *fast = head->next;
     
        while (fast && fast->next)       //Searching for a loop
        {
            if (slow == fast)
                break;
            slow = slow->next;
            fast = fast->next->next;
        }
     
        if (slow == fast)    //Loop exist
        {
            slow = head;
            while (slow != fast->next)
            {
                slow = slow->next;
                fast = fast->next;
            }
     
            fast->next = NULL;    //Removing Loop
        }
    }
     
    int main()
    {
        Node *head = newNode(50);
        head->next = newNode(20);
        head->next->next = newNode(15);
        head->next->next->next = newNode(4);
        head->next->next->next->next = newNode(10);
     
        /* Create a loop for testing */
        head->next->next->next->next->next = head->next->next;
     
        detectAndRemoveLoop(head);
     
        printf("Linked List after removing loop \n");
        printList(head);
     
        return 0;
    }

    Output:

    Linked List after removing loop 
    50 20 15 4 10 

    Explanation:

    Two pointers slow and fast are used to detect loop. Slow contain value of head while fast contain value of head->next. The slow pointer is incremented by one i.e slow->next and fast pointer by two i.e fast->next->next inside while loop and  if loop exist the slow pointer equals fast pointer, the while loop breaks which checks detection of loop. If loop does not exist then in while fast->next is NULL and while loop ends. For removing loop fast->next should be equal to NULL.

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: