Remove duplicate from linked list

Question

I have written the code to remove duplicate from linked list, but I am not able to identify my mistake. Any possible suggestion or help would be appreciated.

#include <bits/stdc++.h>
using namespace std;

//Compiler version g++ 6.3.0

struct Node{
  int data;
  Node *next;
  Node(int x){
    data=x;
    next=NULL;
  }
};

void fun(Node *head){
  Node *curr;
  //Node *temp=curr->next;
  //Node *prev;
  Node *ptr;
  for(curr=head;curr!=NULL;curr=curr->next){
    for(ptr=curr;ptr!=NULL;ptr=ptr->next){
      if(curr->data==ptr->data){
        Node *hold=ptr->next;   //to hold duplicate
        ptr->next=ptr->next->next;
        delete(hold);
      }
      //cout<<curr->data<<endl;
    }    
  }
}

void print(Node *head){
  Node *move=head;
  while(move!=NULL){
    cout<<move->data;
    move=move->next;
  }
}

int main()
{
  int n,data1;
  cin>>n;
  cin>>data1;
  Node *head=new Node(data1);
  Node *temp=head;
  while(n-1!=0){
    int x;
    cin>>x;
    temp->next=new Node(x);
    temp=temp->next;
    n--;
  }
  
  fun(head);
  print(head);
}

Is there any mistake in the fun function or in calling the fun function? I think this is likely, but I am not able to figure it out.

*I think most probably but I am not able to figure out.* -- However you wrote the code, so why is it not possible for you to debug the code that you wrote? When you wrote the code, you must have had a plan written on paper beforehand -- so write the code so it follows your plan, or fix the code you wrote so that it does follow your plan correctly, or your plan was wrong and you need to start over. — PaulMcKenzie, Aug 16 '21 at 00:44
When you delete, this advances forward. `ptr->next=ptr->next->next` then, the loop increment advances again, so you skip one element. — Jeffrey, Aug 16 '21 at 00:45
Also, I bet a simple linked list of 3 elements should have been tested, demonstrating the error, thus easier to debug to see what the issue is. — PaulMcKenzie, Aug 16 '21 at 00:49
One important point that PaulMcKenzie didn't explictly mention: *SINGLE STEP THROUGH YOUR CODE IN THE DEBUGGER*. Learning to use the debugger is one of the most *IMPORTANT* skills you need to know. If you're not already familiar with your compiler's debugger, and how to use it - now is a great time to learn! — paulsm4, Aug 16 '21 at 01:07
*"I am not able to identify my mistake"* -- why do you believe there is a mistake? What are the symptoms? (This both helps future readers with the same issue find this question, and help current readers pinpoint which of your mistakes you are currently working on.) — JaMiT, Aug 16 '21 at 01:14

sharkeater123 · Answer 1 · 2021-08-16T01:01:04.197

0

Node *hold=ptr->next;   //to hold duplicate
ptr->next=ptr->next->next;
delete(hold);

Here, you're holding the next ptr, which is not what the duplicate is. Node *hold = ptr is the duplicate, but since you don't have a prev ptr, you can't remove this duplicate.

edited Aug 16 '21 at 01:01

answered Aug 16 '21 at 00:54

sharkeater123

77
1
6

Job_September_2020 · Answer 2 · 2021-08-16T01:10:05.503

I believe the main error is in your original for loop, where you do not traverse and process the nodes in the linked list correctly.

I have fixed your for loop, and it works now.

Also, I have removed your statement #include <bits/stdc++.h> and using namespace std; with #include <iostream>. Instead, I have used std::in and std::out.

Here are the 2 reasons for not to include #include <bits/stdc++.h> and using namespace std;:

https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h"

Why is "using namespace std;" considered bad practice? in your program.

Here is my new code that works:

#include <iostream>

//Compiler version g++ 6.3.0

struct Node{
  int data;
  Node *next;
  Node(int x){
    data=x;
    next=NULL;
  }
};

void fun(Node *head){
  Node *curr;
  //Node *temp=curr->next;
  //Node *prev;
  Node *ptr;
  for(curr=head;curr!=NULL;curr=curr->next){
      
      if (curr->next == NULL)
         return;
      
    for(ptr=curr->next;ptr!=NULL;ptr=ptr->next){
      if(curr->data==ptr->data){
        Node *hold=ptr;   //to hold duplicate
        curr->next=ptr->next;
        delete(hold);
      }
      else
          break;
      
      //cout<<curr->data<<endl;
    }    
  }
}

void print(Node *head){
  Node *move=head;
  while(move!=NULL){
    std::cout<<move->data;
    move=move->next;
  }
}

int main()
{
  int n,data1;
  std::cin>>n;
  std::cin>>data1;
  Node *head=new Node(data1);
  Node *temp=head;
  while(n-1!=0){
    int x;
    std::cin>>x;
    temp->next=new Node(x);
    temp=temp->next;
    n--;
  }
  
  fun(head);
  print(head);
}

If you run into any other issue during testing, please let me know. But, the code above works for my test cases.

Thanks for help, but for sample input-1 8 3 5 7 9 10 15 9 it is giving a wrong output-1 8 3 5 7 9 10 15 9 ,but the correct output is 1 8 3 5 7 9 10 15. I will also try to figure it out. Thanks a lot for the help. — Segmentation fault, Aug 16 '21 at 08:28
@Segmentationfault, Oh. I did not know that your linked list is unsorted. Can you check to see if your assignment actually states that the linked list is unsorted ? If yes, then another solution would be faster : using an ```unordered_map```. — Job_September_2020, Aug 16 '21 at 09:13

score 0 · Answer 3 · answered Aug 16 '21 at 02:23

0

Maybe you delete the wrong node. condition in if could be something like :

if(curr->data==ptr->next->data) {
    //delete ptr->next，
}

Ofcause, ptr->next should be checked before if.

answered Aug 16 '21 at 02:23

user7663993

16
1

Remove duplicate from linked list

3 Answers3