How do I solve "remove duplicates" question in singly linked list?

Question

Here, I have written a code to implement a singly linked list in C++. Then I have made a function to remove duplicates from the list if any. My program is working perfectly but when I call remove duplicate function its not working , not giving any results. I have tried solving it for more than 10hrs. I think the problem is on delete function but I don't know how to solve it.

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

class node{
    public:
    int data;
    node *next;
    node(int d)
    {
        this->data=d;
        this->next=nullptr;
    }
};

class ll
{
    private:
    node *head=nullptr;
    node *tail=nullptr;
    public:
    void inserthead(int value)
    {
        node *newnode=new node(value);
        if(head==nullptr)
        {
            head=newnode;
            tail=newnode;
        }
        else{
            newnode->next=head;
            head=newnode;
        }
    }
    void inserttail(int value)
    {
        node *newnode=new node(value);
        if(tail==nullptr)
        {
            head=newnode;
            tail=newnode;
        }
        else{
            tail->next=newnode;
            tail=newnode;
        }
    }
    void print()
    {
        node *temp=head;
        while(temp!=nullptr)
        {
            cout<<endl<<temp->data<<endl;
            temp=temp->next;
        }
    }
    void deletenode(int value)
    {
        node *currnode=head;
        int c=0;
        while(currnode!=nullptr)
        {
            if(currnode->data==value)
            {
                break;
            }
            currnode=currnode->next;
            c++;
        }
        if(c==0)
        {
            head=head->next;
            delete currnode;
        }
        else if(c!=0 && currnode->next!=nullptr)
        {
            node *temp1=head;
            int ct=0;
            while(ct<c-1)
            {
                temp1=temp1->next;
                ct++;
            }
            ct=0;
            node *temp2=head;
            while(ct<c+1)
            {
                temp2=temp2->next;
                ct++;
            }
            temp1->next=temp2;
            delete currnode;
        }
        else
        {
            node *temp=head;
            int ct=0;
            while(ct<c-1)
            {
                temp=temp->next;
                ct++;
            }
            temp->next=nullptr;
            tail=temp;
            delete currnode;
        }
    }
    void removeduplicates()
    {   
        node *curr=head;
        while(curr!=nullptr)
        {
            node *compare=curr->next;
            while(compare!=nullptr)
            {
                if(compare->data==curr->data)
                {
                    deletenode(compare->data);
                }
                compare=compare->next;
            }
            curr=curr->next;
        }
    }
};

int main()
{
    ll l1;
    l1.inserthead(10);
    l1.inserthead(10);
    l1.inserttail(9);
    l1.inserttail(8);
    l1.inserttail(11);
    l1.removeduplicates();
    l1.print();
    return 0;
}

Answer 1

Some of the issues:

• In removeduplicates, when deletenode(compare->data) has been called, the node referenced by curr will have been deleted (but see next point), and so the next statement curr=curr->next; makes an invalid dereferencing. You can avoid this in many ways. One way is to not use deletenode at all (see other points below), but to define a function that will remove the next node after a given node. You would call it with curr as argument.
  And after that removal you should not do compare=compare->next; but compare=curr->next;.
• Assuming that removeduplicates is only intended to remove duplicates that are adjacent, you can still have an issue if a value occurs multiple times, but not always adjacent. Take for instance the list 1→2→1→1: At the third node, your code will call deletenode(1), but that will delete the first node, not the "duplicate" one! Again, this means you should not use deletenode here, since you don't want to search for a value, but indicate exactly which node to delete.
• deletenode never updates tail. Yet it should do so when it happens to delete the tail node.
• It doesn't happen in your case, but if deletenode were called when the list is empty, then head=head->next; will dereferrence a null pointer and delete currnode; will attempt to free memory pointed by a null pointer.

Some other remarks:

• Don't include stdio.h in C++ but iostream

• Don't use using namespace std;

• Don't include bits/stdc++.h

• Split logic in different functions. This is mostly true for deletenode, which really has two parts: searching for the value, and the actual removal. You could have functions like delete_head, delete_successor, find, ...

• In deletenode:

  • the test else if ( c!=0 && is unnecessary, as c couldn't be zero, as the case has already been dealt with. Remove that condition.
  • Don't use that c variable at all. All you need is deal with the boundary case where the list is empty, and where the list starts with the value that needs to be removed.
  • The case where currnode->next is not null is not really a special case. You can deal with this case just like with the alternative case.
  • The loop to find temp2 is unnecessary, as temp2 will always end up being currnode->next. It is a waste of effort.
  • The loop to find temp could be omited if in the very first loop you would stop one step earlier. All you really need (in the non-boundary cases) is the node that precedes the node to delete. This calls for a function named delete_successor

• In removeduplicates:

  • It should not use deletenode: that function is intended to search for a node to be deleted, while here you already know which one has to be deleted (compare), so all that looping in deletenode is not relevant for this use case.
  • The previous point also highlights that the name of the function deletenode is misleading. It would be the appropriate name is the argument was a node, but as it has to search for a key, it could be better named delete_first_occurrence or something similar.

• The idea to maintain a tail reference could in some cases be useful, but more often in doubly linked lists. In your case it serves no purpose, and only adds the burden to keep it updated, without any benefit. I've kept it in the code below, but if there is no other benefit (in code you have not shared) then ditch it.

• If you're not using camelCase, then use snake_case for your functions. I'd suggest using PascalCase for class names, and using descriptive names (not ll, but LinkedList). This improves the readability.

Proposed correction

#include <iostream>

class Node {
public:
    int data;
    Node *next = nullptr;
    
    Node(int d): data(d) {}
};

class LinkedList {
private:
    Node *head = nullptr;
    Node *tail = nullptr;

public:
    void insert_head(int value) {
        Node *newnode = new Node(value);
        if (!head) {
            tail = newnode;
        } else {
            newnode->next = head;
        }
        head = newnode;
    }

    void insert_tail(int value) {
        Node *newnode = new Node(value);
        if (!tail) {
            head = newnode;
        } else {
            tail->next = newnode;
        }
        tail = newnode;
    }

    void print()
    {
        Node *temp = head;
        while (temp) {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        }
        std::cout << "(null)" << std::endl;
    }

    void delete_head() {
        if (!head) { // nothing to delete
            return;
        }
        Node *temp = head;
        head = head-> next;
        delete temp;
        if (!head) {
            tail = nullptr;
        }
    }

    void delete_successor(Node *prevnode) {
        if (!prevnode) { // special case
            return delete_head();
        }
        if (!head || !prevnode->next) { // nothing to delete
            return;
        }
        Node *temp = prevnode->next;
        prevnode->next = prevnode->next->next;
        delete temp;
        if (!prevnode->next) {
            tail = prevnode;
        }
    }

    Node* find_predecessor(int value) {
        if (!head || head->data == value) {
            return nullptr; // Can mean "head has the value"
        }
        Node *prevnode = head;
        while (prevnode->next && prevnode->next->data != value) {
            prevnode = prevnode->next;
        }
        return prevnode; // Could be tail node, meaning "value not found"
    }

    void delete_first_occurrence(int value) {
        delete_successor(find_predecessor(value));
    }

    void remove_duplicates() {   
        Node *curr = head;
        while (curr) {
            while(curr->next && curr->next->data == curr->data) {
                delete_successor(curr);
            }
            curr = curr->next;
        }
    }
};

int main()
{
    LinkedList l1;
    l1.insert_head(10);
    l1.insert_head(10);
    l1.insert_tail(9);
    l1.insert_tail(8);
    l1.insert_tail(8);
    l1.insert_tail(11);
    l1.insert_tail(11);
    l1.insert_tail(11);
    l1.insert_tail(8);
    l1.insert_tail(8);
    l1.remove_duplicates();
    l1.print();
    return 0;
}

There much more you can do to improve, like using smart pointers, so you don't have to explicitly execute delete, but then we come to the point that you should just not implement a linked list from scratch, and use the one from the standard library. But I assume this is an assignment where you're asked to define the linked list data structure yourself.

Answer 2

Note in C++ you would probable not use your own list class but this :

#include <list>
#include <algorithm>
#include <iostream>

int main()
{
    std::list<int> values{ 1,2,3,4,3,2,5,6,7,3,2,4,5,6 };
    
    values.sort();
    values.unique();

    for (const auto value : values)
    {
        std::cout << value << " ";
    }

    return 0;
}