C Programming - Removing Loop from a Linked List

Given a Linked List which has loop within it, remove the looping with minimum complexity.

Node:

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

Explanation:
If Linked List is as given below

1->2->3->4->5->6
          |_________|

What we are doing in this solutions is inserting an element who data element is known to us between every node, such that it looks like

1->B->2->B->3->B->4->B->5->B->6
                    |__________________|

So the before inserting after the node which is looping we are checking whether that node next to the next is B or not, thereby finding out the looping node.

Solution:


/* Function which removes Loop from LL */

void vRemoveLoop(Node *head1)
{
    Node *tmp;
    Node *tmp1 = NULL;
    for(tmp = head1; tmp!= NULL; tmp = tmp1) {
 Node *temp = (Node *) malloc(sizeof(Node));
 temp->data = (int) temp;
 temp->next = NULL;
 if( (tmp->next != tmp) && (tmp->next->next->data !=  (int) tmp->next->next) ) 
         temp->next = tmp->next;
     tmp->next = temp;
            tmp1 = temp->next;
    }

    for(tmp = head1; tmp!= NULL; tmp = tmp->next) {
        tmp1 = tmp->next;
        tmp->next = tmp->next->next;
        if (tmp1->next != NULL ) 
            tmp1->next = tmp1->next->next;
        else
            tmp1->next = NULL;
    }
}


Post in your comments!

Labels:

About this entry

You’re currently reading “C Programming - Removing Loop from a Linked List,” an entry on ANOOB BACKER Technical Blog

Published:
11:10 am
by -