Skip to content
Remove Duplicates from Sorted Linked List

Remove Duplicates from a Sorted Linked List

Remove duplicates from a sorted linked list. In this problem, as the list is already sorted, the duplicates are next to one another and easy to identify. However, as we are dealing with a linked list we need to connect the nodes carefully.

Example

Input

[1] => [2] => [2] => [3] => [3] => [5]

Output, after removing duplicates

[1] => [2] => [3] => [5]

Solution Approach

First, we start iterating through each node in the Linked List. Then once we encounter a duplicate in that case the next node is the same as the current node and we keep moving to the next node until the end of the duplicate, and as we move forward, we assign the next of next to the current and delete the old next node, look at the example below

Remove duplicates
Removing Duplicates – Linked List

Program to Remove Duplicates – Sorted Linked List

Below is the main logic. Here, first means the HEAD of the Linked List

void Remove Duplicates()
{
    Node *p = first, *q = p->next;
    while (q != NULL)
    {
        if (p->data != q->data)
        {
            p = q;
            q = q->next;
        }
        else
        {
            p->next = q->next;
            free(q);
            q = p->next;
        }
    }
}

Code in C++

Here’s the full program to remove duplicates from a linked list.

#include <iostream>
using namespace std;

class Node
{
public:
    int data;
    Node *next;
};

class LinkedList
{
private:
    Node *first;

public:
    LinkedList() { first = NULL; }
    LinkedList(int A[], int n);
    //destructor
    ~LinkedList();
    void RemoveDuplicate();
    void Display();
};

void LinkedList::RemoveDuplicate()
{
    Node *p = first, *q = p->next;
    while (q != NULL)
    {
        if (p->data != q->data)
        {
            p = q;
            q = q->next;
        }
        else
        {
            p->next = q->next;
            free(q);
            q = p->next;
        }
    }
}

LinkedList::LinkedList(int A[], int n)
{
    Node *last, *t;
    int i = 0;

    first = new Node;
    first->data = A[0];
    first->next = NULL;
    last = first;

    for (i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

LinkedList::~LinkedList()
{
    Node *p = first;
    while (first)
    {
        first = first->next;
        delete p;
        p = first;
    }
}

void LinkedList::Display()
{
    Node *p = first;

    while (p)
    {
        cout << p->data <<" " ;
        p = p->next;
    }
    cout << endl;
}

int main()
{
    int A[] = {11, 22, 22, 44, 44, 55};
    LinkedList l(A, 6);
    l.Display();
    l.RemoveDuplicate();
    l.Display();
    l.~LinkedList();
    // reverse a linked list
    return 0;
}

Output

11 22 22 44 44 55
11 22 44 55

Conclusion

This post is a part of my #30DaysChallenge to write a blog post every day on what I learn, Do what you love!~ Abhiram Reddy.

Tags: