what am I doing wrong here? can someone fix my code?
TEST CASES FAILED
Please mention the question name also so that i can check with the test cases.
Your code is giving segmentation fault. Most probably this is because, somewhere you are trying to access node->next where node is NULL. You cannot perform such operation on a NULL node. This is occurring in the removecycle function. Cross check your code and try to correct it.
it’s cycle detection and removal
the question name
can you comment the error?
In line 39 and 40, when i->next= Null, then j=Null. And in the loop you are performing j=j->next and checking j->next!=NULL… this will cause segmentation fault.
Please use the Floyd cycle detection algorithm. There must be its video in your course playlist. Watch it and then proceed with this question.
bool floydCycleRemoval(Node *head)
{
/* Code here */
Node*slow=head,*fast=head->next,*temp=NULL;
while(fast&&fast->next){
if(slow==fast)break;
slow=slow->next;
fast=fast->next->next;
}
// if cycle not present
if(fast==NULL||fast->next==NULL)return false;
/// now count no of Nodes in loop
int k=1;
slow=slow->next;
while(slow!=fast){
k++;
slow=slow->next;
}
// now point slow to head and fast to k Node ahead
slow=head;
fast=head;
while(k--){
fast=fast->next;
}
/// move slow and fast one by one
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
// now move only fast
while(fast->next!=slow){
fast=fast->next;
}
fast->next=NULL;
return true;
}
this is correct way to do it
floyd is giving tle
I tried using that too here is the code
#include
using namespace std;
class node{
public:
int data;
node * next;
node(int d){
data=d;
next=NULL;
}
};
void push(node *&head,int data){
node *temp=head;
node *n=new node(data);
if(head!=NULL){
while(temp->next!=head){
temp=temp->next;
}
temp->next=n;
n->next=head;
}
else{
n->next=n;
head=n;
}
}
bool found(node *head,node *temp,int data){
// node *temp=head;
while(temp!=head){
if(temp->data==data){
return true;
}
temp=temp->next;
}
return false;
}
void buildcycle(node *&head){
node *temp=head;
// node *p;
bool present=false;
while(temp->next!=head){
// if(found(temp->next,temp->data)){
if(found(head,temp->next,temp->data)){
// p=temp;
present=true;
break;
}
temp=temp->next;
}
// while(temp->next!=head){
// temp=temp->next;
// }
// temp->next=p;
if(present){
int data=temp->data;
while(temp->next->data!=data){
temp=temp->next;
}
temp->next=head;
}
}
void cycleremoval(node* &head){
node *slow=head;
node *fast=head;
node *prev;
while(fast!=NULL && fast->next!=NULL){
prev=slow;
fast=fast->next->next;
slow=slow->next;
if(slow==fast){
break;
}
}
slow=head;
while(slow!=fast){
prev=fast;
slow=slow->next;
fast=fast->next;
}
prev->next=NULL;
}
void print(node *head){
while(head!=NULL){
cout<<head->data<<" ";
head=head->next;
}
//cout<<“length:”<<length(head)<<endl;
cout<<endl;
}
void printc(node *head){
node *temp=head;
while(temp->next!=head){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<temp->data;
}
int main(){
node * head=NULL;
while(1)
{
int n;
cin>>n;
if(n==-1)
{
break;
}
push(head,n);
}
buildcycle(head);
cycleremoval(head);
print(head);
return 0;
}
Check the optimized solution from here.
I did but TLE persists
check my code
#include
using namespace std;
class node{
public:
int data;
node * next;
node(int d){
data=d;
next=NULL;
}
};
void push(node *&head,int data){
node *temp=head;
node *n=new node(data);
if(head!=NULL){
while(temp->next!=head){
temp=temp->next;
}
temp->next=n;
n->next=head;
}
else{
n->next=n;
head=n;
}
}
bool found(node *head,node *temp,int data){
// node *temp=head;
while(temp!=head){
if(temp->data==data){
return true;
}
temp=temp->next;
}
return false;
}
void buildcycle(node *&head){
node *temp=head;
// node *p;
bool present=false;
while(temp->next!=head){
// if(found(temp->next,temp->data)){
if(found(head,temp->next,temp->data)){
// p=temp;
present=true;
break;
}
temp=temp->next;
}
// while(temp->next!=head){
// temp=temp->next;
// }
// temp->next=p;
if(present){
int data=temp->data;
while(temp->next->data!=data){
temp=temp->next;
}
temp->next=head;
}
}
void cycleremoval(node* &head){
node *slow=head;
node *fast=head;
node *prev;
while(fast!=NULL && fast->next!=NULL){
prev=slow;
fast=fast->next->next;
slow=slow->next;
if(slow==fast){
break;
}
}
slow=head;
while(slow!=fast){
prev=fast;
slow=slow->next;
fast=fast->next;
}
prev->next=NULL;
}
void print(node *head){
while(head!=NULL){
cout<data<<" ";
head=head->next;
}
//cout<<“length:”<<length(head)<<endl;
cout<<endl;
}
void printc(node *head){
node *temp=head;
while(temp->next!=head){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<temp->data;
}
int main(){
node * head=NULL;
while(1)
{
int n;
cin>>n;
while(n–){
break;
}
push(head,n);
}
buildcycle(head);
cycleremoval(head);
print(head);
return 0;
}
Try with hashing based approach. Which is method 4 in above link.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.