 # 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

`` =>  =>  =>  =>  => ``

Output, after removing duplicates

`` =>  =>  => ``

## 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 ### 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;
};

{
private:
Node *first;

public:
LinkedList() { first = NULL; }
//destructor
void RemoveDuplicate();
void Display();
};

{
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;
}
}
}

{
Node *last, *t;
int i = 0;

first = new Node;
first->data = A;
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;
}
}

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

{
Node *p = first;

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

int main()
{
int A[] = {11, 22, 22, 44, 44, 55};
l.Display();
l.RemoveDuplicate();
l.Display();
``````11 22 22 44 44 55