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: C

## About this entry

You’re currently reading “

- Published:
- 11:10 AM
- by --

## 0 Comments (Post a Comment)