Write a C program that will determine whether or not a given singly-linked list

Question

Write a C program that will determine whether or not a given singly-linked list structure contains a loop. The program must always terminate; in other words, if there is a loop it must determine this and print this result in a finite amount of time. Assume that you start from a pointer to the head of the list and that the end of the list is marked by having a NULL pointer in the next-element pointer field. You cannot make any assumptions about how big the potential loop is or where it might be in the data structure. You should test you problem with both a normal linked list and one containing a loop.

Explanation / Answer

#include<iostream>

using namespace std;

#include<stack>

#include<stdio.h>

#include<conio.h>

#include<string>

#include<stdlib.h>

struct node

{int data;

struct node *next;

};

struct node *head,*tail,*temp;

void addatend(int);

void display();

void loop_detect(struct node*);

int main()

{ head=NULL;

tail=NULL;

temp=NULL;

int n;

printf("enter the values in the linked list:");

while(1)

{

scanf("%d",&n);

if(n==-1)

break;

else

addatend(n);

}

printf("the original given limked list is : ");

display();

loop_detect(head);

//create a loop for detection

head->next->next->next=head->next;

loop_detect(head);

getch();

return 0;

}

void display()

{cout<<endl;

struct node *p1;

p1=head;

while(p1!=NULL)

{printf(" %d ",p1->data);

p1=p1->next;

}

}

void addatend(int val)

{

temp=(struct node*)malloc(sizeof(struct node));

temp->data=val;

temp->next=NULL;

if(head==NULL)

{head=temp;

tail=temp;

}

else

{

tail->next=temp;

tail=temp;

}

}

void loop_detect(struct node *head)

{ int flag=0;

struct node *slow,*fast;

slow=head;

fast=head;

while((slow!=NULL)&&(fast!=NULL)&&(fast->next!=NULL)&&(fast->next->next!=NULL))

{slow=slow->next;

fast=fast->next->next;

if(slow==fast)

{printf(" there is a loop in the linked list ");flag=1;

return;

}

}

if(flag==0)

printf(" there is NO loop in the linked list ");

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.