Wednesday, August 1, 2012

loop in linked list C program!!

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");
}


1 comment:

Anonymous said...

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

Popular Posts