C Programming - Removing Loop from a Linked List

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


struct NODE {
int data;
struct NODE *next;

If Linked List is as given below


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


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.


/* 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;
tmp1->next = NULL;

Post in your comments!


About this entry