Wednesday, August 1, 2012

loop in linked list C program!!

Below is the C  program for finding the loop in a linked list 
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
    else    if(tempHead->next==NULL)  // if the list is having only one node
        tempHead->next = newNode;
        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)
        temp = temp->next;

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 second move is equal to tempOne then there is loop
                return 1;
            tempTwo=tempTwo->next;   // second move

        tempOne = tempOne->next;  // one move
    return 0;
    Node *head = NULL;
    int i;
    for (i=1;i<=10;i++)
        head = append(head,i*10);
    head = append(head,101); // this element for making loop in the list
        printf("loop found in the list\n");
        printf("no loop in the list\n");

1 comment:

Anonymous said...

You have published an awesome site.
Here is my page :: Digital Printing Melbourne

Popular Posts