I have to make a program to count the number of occurrences of a given key in a singly linked list and then delete all the occurrences. For example, if given linked list is 1->2->1->2->1->3->1 and given key is 1, then output should be 4. After deletion of all the occurrences of 1, the linked list is 2->2->3.

I tried making a program that removes duplicate elements from a linked list and count the number of occurrence of the duplicate element output for my program is

Your linked list is 1 2 1 2 1 3 1 
Enter a number: 1
Number of occurance is: 4
After deleting repeated elements: 
Your linked list is 2 2 1 3 1 

I am going to add third case to remove element from the end soon but I need help in this function . Here I am only able to remove one '1' why is this happening please help

struct Node* ptr2= head;
    struct Node* ptr3= head->next;
    while(ptr3!=NULL)
    {
        if(ptr3->data==x)
        {
            ptr2->next=ptr3->next;
        }
        ptr2=ptr2->next;
        ptr3=ptr3->next;
    }
    cout<<"Number of occurance is: "<<count<<endl;
   return head;

whole program is :- 

#include<iostream>
using namespace std;
struct Node
{
    int data;
    struct Node* next;
};
void traversal(struct Node* head)
{
    cout<<"Your linked list is ";
    struct Node* ptr = head;
    while(ptr!=NULL)
    {
        cout<<ptr->data<<" ";
        ptr=ptr->next;

    }
}
struct Node* deleterepeated(struct Node* head, int x)
{
    int s=0;//number of elements in linked list
    struct Node* p = head;
    while(p!=NULL)
    {
        p=p->next;
        s  ;
    }
    struct Node* ptr = head;
   
    int count=0;
    while(ptr!=NULL)
    {
        if(ptr->data == x)
        {
            if(count==0)
            {
                head=ptr->next;
            }
            count  ;
        }
    
        ptr=ptr->next;
    
    }

    struct Node* ptr2= head;
    struct Node* ptr3= head->next;
    while(ptr3!=NULL)
    {
        if(ptr3->data==x)
        {
            ptr2->next=ptr3->next;
        }
        ptr2=ptr2->next;
        ptr3=ptr3->next;
    }
    cout<<"Number of occurance is: "<<count<<endl;
   return head;
}
int main()
{
    struct Node* head;
    struct Node* val1;
    struct Node* val2;
    struct Node* val3;
    struct Node* val4;
    struct Node* val5;
    struct Node* val6;

    head= (struct Node*)malloc(sizeof(struct Node));
    val1= (struct Node*)malloc(sizeof(struct Node));
    val2= (struct Node*)malloc(sizeof(struct Node));
    val3= (struct Node*)malloc(sizeof(struct Node));
    val4= (struct Node*)malloc(sizeof(struct Node));
    val5= (struct Node*)malloc(sizeof(struct Node));
    val6= (struct Node*)malloc(sizeof(struct Node));

    head->data=1;
    val1->data=2;
    val2->data=1;
    val3->data=2;
    val4->data=1;
    val5->data=3;
    val6->data=1;

    head->next=val1;
    val1->next=val2;
    val2->next=val3;
    val3->next=val4;
    val4->next=val5;
    val5->next=val6;
    val6->next=NULL;

    traversal(head);
    cout<<endl;

    cout<<"Enter a number: ";
    int x;
    cin>>x;

    head=deleterepeated(head,x);
    cout<<"After deleting repeated elements: "<<endl;
    traversal(head);


    return 0;
}

CodePudding user response：

It is very easy to do if you use the standard linked list implementation:

#include <iostream>
#include <list>

int main() {
    std::list<int> list{1, 2, 1, 2, 1, 3, 1};
    int nOnes = 0;
    for (auto it = list.begin(), end = list.end(); it != end; /*no op*/) {
        if (*it == 1) {
              nOnes;
            it = list.erase(it); // remove element idiom
        } else {
              it;
        }
    }

    std::cout << "Removed " << nOnes << " item(s)\n"
              << "Remains: \n";
    for (auto const e : list) {
        std::cout << e << '\n';
    }
}

As a side-note, it is even nicer with a vector:

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec{1, 2, 1, 2, 1, 3, 1};
    auto const nOnes = vec.end() - std::remove(vec.begin(), vec.end(), 1);
    vec.resize(vec.size() - nOnes);
}

CodePudding user response：

so , you have a little tiny mistakes in your code , I edited it out , all of the edits are in the function named deleterepeated and here is my solution , not the best but it will work for your case :

EDIT: I removed unnecessary things in the code to be only one big loop , also I found a bug in my previous code and edit it out here in the new version , this is only the deleterepeated function

    struct Node* deleterepeated(struct Node* head, int x)
    {
        int count = 0;
        struct Node* ptr2 = head;
        struct Node* ptr3 = ptr2->next;
        struct Node* temp;
        while (ptr3 != NULL)
        {
            if (head && head->data == x)    // here is the part of deleting the head if it matches
            {
                temp = head;
                head = head->next;
                free(temp);
                ptr2 = head;
                ptr3 = head->next;
            }
            else if (ptr3 && ptr3->data == x)
            {
                temp = ptr3;
                ptr2->next = ptr3->next;
                free(temp);           // you have to free memory to avoid memory leak
                ptr3 = ptr2->next;
                count  ;
            }
            else
            {
                ptr2 = ptr2->next;
                ptr3 = ptr3->next;
            }

        }
        cout << "Number of occurance is: " << count << endl;
        return head;
    }

picture of the results: