Below is the C program for finding the loop in a linked list
#include<stdio.h> #include<stdlib.h> struct node { int info; struct node *next; }; typedef struct node Node; Node* append(Node *h, int info) { Node *tempHead=h; Node *newNode = (Node*)malloc(sizeof(Node)); newNode->info = info; newNode->next = NULL; if(tempHead == NULL) // if the list has zero elements. make new node as a head { h=newNode; } else if(tempHead->next==NULL) // if the list is having only one node { tempHead->next = newNode; } else { Node *tempNode = h; // if the list has more than one node, so moving to the last node while(tempNode->next != NULL) { tempNode = tempNode->next; } tempNode->next = newNode; // appending the new node at the end } // this is for making the list circular/loop if(info == 101) newNode->next = h; return h; } /***************************************************************************** for displaying the nodes in the list. Dont call this function if the list contains loop. if you call you wont get the end, becaue there is no NULL in the list *****************************************************************************/ void display(Node *h) { Node *temp = h; while (temp->next!=NULL) { printf("%d->",temp->info); temp = temp->next; } printf("%d\n",temp->info); } /************************************************************************************* let me explain the concept first. for finding the loop in a single linked list, need to take two temparty nodes tempOne and tempTwo, move temOne node one level and move tempTwo two levels(tempTwo->next->next) until tempTwo/tempOne reaches NULL, if the list contains loop somewhere, these two nodes must be met/same, if not met/same, there is no loop in the list ***************************************************************************************/ int loop(Node *head) { Node *tempOne = head; Node *tempTwo = head; while( tempTwo->next!=NULL ) { tempTwo = tempTwo->next; // one move if(tempTwo->next!=NULL) { // if second move is equal to tempOne then there is loop if(tempTwo->next==tempOne) return 1; else tempTwo=tempTwo->next; // second move } tempOne = tempOne->next; // one move } return 0; } main() { Node *head = NULL; int i; for (i=1;i<=10;i++) { head = append(head,i*10); } display(head); head = append(head,101); // this element for making loop in the list i=loop(head); if(i) printf("loop found in the list\n"); else printf("no loop in the list\n"); }
2 comments:
You have published an awesome site.
Here is my page :: Digital Printing Melbourne
Interesting readd
Post a Comment