Note 1

Take Note:

Take a note while surfing.





Note With Ink

Give your Note a Colorful Tag.




Easy to Access

Stay on same information and in Sync wherever you are.

Note 2

Take Note:

Organize your information,It may take Shape.





Think With Ink

Differ your Content by Color.




Easy to Access

Easy to pull up your content from anywhere anytime.

Note 3

Take Note:

Don't Let information to miss,Because it take shape





Note With Ink

Simple an Easy Way to take a note.




Easy to Access

Get the same in next visit.

Program Discussion :: Basics
Home > Programs > Basics

109. Write a program to find the loop in linklist and remove the loop in linklist.

Answer:

#include <stdio.h>
#include <stdlib.h>
#include<iostream>
using namespace std;
struct node{
    int val;
    struct node *next;
};
void print_list(struct node *head)
{
    cout<<"H->";
    while(head)
    {
        cout<< head->val;
        head = head->next;
    }
    cout<<"|||\n";
}
void insert_front(struct node **head, int value)
{
    struct node * new_node = NULL;
    new_node = (struct node *)malloc(sizeof(struct node));
    if (new_node == NULL)
    {
        cout<<"Failed to insert element. Out of memory";
    }
    new_node->val = value;
    new_node->next = *head;

    *head = new_node;
}
void create_loop(struct node *head)
{
    struct node *tmp = head;

    while(tmp->next) tmp = tmp->next;

    tmp->next = head->next;
}

void print_loop(struct node *head)
{
    int n = 25;
    cout<<"H->";

    while(n--)
    {
        cout<<head->val;
        head = head->next;
    }

    cout<<"|||\n";
}

void detect_loop(struct node *head)
{
    struct node *slow = head;
    struct node *fast = head;

    while(slow && fast->next && fast->next->next)
    {
        if ((slow == fast->next) || (slow == fast->next->next ))
        {
            cout<<"Linked list has a loop.\n";
            return;
        }

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

    cout<<"Linked list does not have any loop.\n";
}

void remove_loop(struct node *head, struct node *loop_node)
{
    struct node *near = head;
    struct node *far = head;
    struct node *ptr = loop_node;
    struct node *prev = NULL;

    while(ptr->next != loop_node)
    {
        ptr = ptr->next;
        far = far->next;
    }

    prev = far;
    far = far->next;

    while(near != far)
    {
        prev = far;
        far = far->next;
        near = near->next;
    }

    prev->next = NULL;
}

void detect_and_remove_loop(struct node *head)
{
    struct node *slow = head;
    struct node *fast = head;

    while(slow && fast->next && fast->next->next)
    {
        if ((slow == fast->next) || (slow == fast->next->next ))
        {
            cout<<"Linked list has a loop.\n";
            remove_loop(head, slow);
            return;
        }

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

   cout<<"Linked list does not have any loop.\n";
}

void main()
{
    int count = 0, i, val;
    struct node * head = NULL;

    cout<<"Enter number of elements: ";
  cin>>count;

    for (i = 0; i < count; i++)
    {
        cout<<"Enter ith element: "<< i;
        cin>>val;
        insert_front(&head, val);
    }

    cout<<"Original List: ";
    print_list(head);
    detect_loop(head);

    cout<<"Creating loop...\n";
    create_loop(head);
    cout<<"Printing list with loop";
    print_loop(head);
    detect_loop(head);

    cout<<"Removing loop...\n";
    detect_and_remove_loop(head);
    detect_loop(head);

    cout<<"List after removing loop:\n";
    print_list(head);
}

Post Your Answer Here:

Name *
Email

Language:

Post Your Reply Here:



Language:

Post Your Reply Here: