#include <stdio.h> #include <iostream.h> #include <conio.h> #include <stdlib.h>
ID: 3875283 • Letter: #
Question
#include <stdio.h>
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
struct stock
{
int data;
struct stock *next;
}*nnode,*ptr,*p,*prev,*start;
class LinkedList
{
public:
LinkedList()
{
start=NULL;
}
void create()
{
nnode=new stock;
cout<<"enter the data you want to enter";
cin>>nnode->data;
nnode->next=NULL;
start=nnode;
}
void addAtBeginning()
{
nnode=new stock;
cout<<"enter the data you want to enter";
cin>>nnode->data;
nnode->next=start;
start=nnode;
}
void addAtLast()
{
for(ptr=start;ptr!=NULL;prev=ptr,ptr=ptr->next);
cout<<"enter the data you want to enter";
nnode=new stock;
cin>>ptr->data;
prev->next=nnode;
nnode->next=NULL;
}
void deleteFirst()
{
ptr=start;
start=ptr->next;
delete(ptr);
}
void deleteLast()
{
for(ptr=start;ptr!=NULL;p=prev,prev=ptr,ptr=ptr->next);
p->next=NULL;
delete(prev);
}
void display()
{
for(ptr=start;ptr!=NULL;ptr=ptr->next)
cout<<ptr->data;
}
int totalNumberOfNodes()
{
stock *ptr;
ptr=start;
int count=0;
while (ptr!=NULL)
{
count++;
ptr=ptr->next;
}
return count;
}
void listCircularOrNot()
{
}
void removeCircularLoop()
{
}
};
int main()
{
int ch;
LinkedList l;
clrscr();
while(1)
{
cout<<"enter choice";
cin>>ch;
switch(ch)
{
case 1:l.create();
break;
case 2:l.addAtBeginning();
break;
case 3:l.addAtLast();
break;
case 4:l.deleteFirst();
break;
case 5:l.deleteLast();
break;
case 6:l.display();
break;
case 7:l.listCircularOrNot();
break;
case 8:exit(1);
default:cout<<"invalid choice";
}
}
getch();
return 0;
}
Write function listCircularOrNot() to find whether a singly linked list is circular or not in other words how to determine whether a singly linked list contains a Loop or not? Also if the linkedList contains loop then write another function removeCircularLoop() to remove the loop from the linked list keeping the entire structure same.
Explanation / Answer
Please find below the code for listCircularOrNot() and removeCircularLoop(). Please find the inline comments for better explanation for these two methods.
listCircularOrNot():
////////////////////////////////////////////////////////
/* listCircularOrNot(): This function detects a loop in the linked list.
* Removes loop if a loop is found.
*/
void listCircularOrNot() {
// create two pointers 'slow' and 'fast'
// slow pointer moves one node at a time, whereas fast moves 2 nodes at a time
struct stock *slow = start, *fast = start;
// Run a loop until the slow and fast pointers are not null.
while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
// If slow and fast meet at some point then there is a loop
if (slow->data == fast->data) {
cout<<" Loop detected in the linked list. Removing loop now!!!";
// remove circular loop
removeCircularLoop(slow);
}
}
}
removeCircularLoop():
////////////////////////////////////////////////////////
/* removeCircularLoop(): This function is used to remove a loop from the linked list.
* Argument: loopNode where the cycle is found.
*/
void removeCircularLoop(stock *loopNode) {
struct stock *ptr1, *ptr2;
// Set ptr1 to the beginning of the list.
// Lets move ptr1 one by one to find the first node in the cycle.
ptr1 = start;
while (1) {
// Now, we need to start a pointer from loopNode and find if it is reachable to ptr2.
ptr2 = loopNode;
while (ptr2->next != loopNode && ptr2->next != ptr1)
ptr2 = ptr2->next;
// A cycle is found out when ptr2's next node is ptr1.
if (ptr2->next == ptr1)
break;
// We need to move ptr1 one by one until ptr2 reaches ptr1. Hence, ptr1 should be moved to next node.
ptr1 = ptr1->next;
}
// After exiting the loop, ptr2 is always the last node in the cycle.
// Remove the cycle by setting ptr's next next to null, which means it is
// no longer pointing to ptr1 and hence, does not create a cycle.
ptr2->next = NULL;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.