Wednesday, January 16, 2008

Finding the loop in Single Linked List

#include <stdio.h>
#include "malloc.h"


struct Node
{
struct Node * next;
int num;
};


void insertIntoLL(struct Node **head, int inum)
{
struct Node* temp;
temp = *head;
if(temp == NULL)
{
temp = (struct Node *) malloc(sizeof(Node));
temp->num = inum;
temp->next = NULL;
*head = temp;
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (struct Node *) malloc(sizeof(Node));
temp->next->num = inum;
temp->next->next = NULL;
}

}
Node* GetNodeAddress(int num, struct Node* head)
{
Node *temp = head;
if(temp->num == num)
return temp;
else
while(temp->next != NULL)
{
if(temp->num == num)
return temp;
temp = temp->next;
}
if(temp->num == num)
return temp;
else
return NULL;
}

void CheckLoopInLL(Node* head)
{
Node * slowGuy = head;
Node * fastGuy = head;
Node *fasterGuy = head;
while(slowGuy != NULL && fastGuy != NULL && fasterGuy != NULL)
{
slowGuy = slowGuy->next;
fastGuy = fastGuy->next->next;
fasterGuy = fasterGuy->next->next->next;
if((slowGuy == fastGuy)(slowGuy == fasterGuy)(fastGuy == fasterGuy))
{
printf("There is a loop");
break;
}

}
}


int _tmain(int argc, _TCHAR* argv[])
{
Node *head = NULL;
insertIntoLL(&head,10);
insertIntoLL(&head,20);
insertIntoLL(&head,30);
insertIntoLL(&head,40);
insertIntoLL(&head,50);
insertIntoLL(&head,60);
insertIntoLL(&head,70);
insertIntoLL(&head,80);
insertIntoLL(&head,90);
insertIntoLL(&head,100);
insertIntoLL(&head,110);
insertIntoLL(&head,120);
insertIntoLL(&head,130);
insertIntoLL(&head,140);
insertIntoLL(&head,150);
insertIntoLL(&head,160);
insertIntoLL(&head,170);
Node* node30 = GetNodeAddress(30,head);
Node* node170 = GetNodeAddress(170,head);
node170->next = node30;
CheckLoopInLL(head);
return 0;
}

Complexity: SIMPLE.

No comments: