Singly Linked List : Remove Duplicates


C++ Program to remove duplicate elements from a sorted singly linked list.
Note: Below program just keeps one copy of the duplicate element and removes the rest.

#include<iostream>

using namespace std;

class Node {
    public:
    int data;
    Node* next;
    Node (int arg_data) : data (arg_data), next (nullptr)
    {}
};

// Remove duplicate elements from the linked list, keeping just one copy
Node* DeleteDuplicates (Node* head) {

    if (head == NULL)
        return head;

    Node * node = head;

    while (node->next != NULL) {

        if (node->next->data != node->data) {
            node = node->next;
        } else {
            Node * tmp = node->next;
            node->next = node->next->next;
            delete tmp;
        }
    }
    return head;
}

void Display (Node * head) {
    Node * node = head;
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    } cout << endl;
}

void CleanUp (Node * head) {
    while(head != NULL) {
        Node * tmp = head->next;
        delete head;
        head = tmp;
     }
}

int main() {

    // 3 -> 3 -> 4 -> 4 -> 5 -> 5
    Node * a = new Node(3);
    Node * b = new Node(3);
    Node * c = new Node(4);
    Node * d = new Node(4);
    Node * e = new Node(5);
    Node * f = new Node(5);

    a->next = b;
    b->next = c;
    c->next = d;
    d->next = e;
    e->next = f;

    cout << "Before removing duplicates" << endl;
    Display(a);
    cout << "After removing duplicates" << endl;
    Node * head = DeleteDuplicates(a);
    Display(head);
    CleanUp(head);

    return 0;
}

Output

Before removing duplicates
3 3 4 4 5 5 
After removing duplicates
3 4 5 

C++ Program to remove all duplicate elements from a sorted singly linked list.

#include<iostream>
#include<set>
using namespace std;

class Node {
    public:
    int data;
    Node* next;
    Node (int arg_data) : data (arg_data), next (nullptr)
    {}
};

Node* DeleteDuplicates (Node* head) {

    if (head == NULL or head->next == NULL) {
        return head;
    }

    set<int> duplicates;
    Node * node = head;

    while (node != NULL) {
        if (node->next != NULL and node->data == node->next->data) {
            duplicates.insert(node->data);
        }
        node = node->next;
    }
    
    // Remove any duplicates at the beginning.
    while (head != NULL and duplicates.find(head->data) != duplicates.end()) {
        Node * tmp = head->next;
        delete head;
        head = tmp;
    }
    
    node = head;
    Node *prev = head;
    // Remove duplicate elements if any from middle / end     
    while (node != NULL) {
        if (duplicates.find(node->data) != duplicates.end()) {
            prev->next = node->next;
            delete node;
            node = prev->next;
        } else {
            prev = node;
            node = node->next;
        }
    }
    return head;
}

void Display (Node * head) {
    Node * node = head;
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    } cout << endl;
}

void CleanUp (Node * head) {
    while(head != NULL) {
        Node * tmp = head->next;
        delete head;
        head = tmp;
     }
}

int main() {

    // 3 -> 3 -> 4 -> 4 -> 5 -> 5 -> 7
    Node * a = new Node(3);
    Node * b = new Node(3);
    Node * c = new Node(4);
    Node * d = new Node(4);
    Node * e = new Node(5);
    Node * f = new Node(5);
    Node * g = new Node(7);

    a->next = b;
    b->next = c;
    c->next = d;
    d->next = e;
    e->next = f;
    f->next = g;

    cout << "Before removing all duplicates" << endl;
    Display(a);
    cout << "After removing all duplicates" << endl;
    Node * head = DeleteDuplicates(a);
    Display(head);
    CleanUp(head);

    return 0;
}

Output

Before removing all duplicates
3 3 4 4 5 5 7 
After removing all duplicates
7


Copyright (c) 2019-2022, Algotree.org.
All rights reserved.