# Remove Duplicate Elements from a Sorted Singly Linked List

A linked list data structure is made up of a set of nodes that are linked together. Every node stores the data as well as the address of the next node.
You have to start somewhere, so we give the first node’s address a special name called HEAD.

The final node in the linked list can also be marked since its next section points to NULL.

You’ve always played the game Treasure Hunt, where each clue contains details about the next clue. That is how a connected list works.

Examples:

Input:

 5 5 6 6 7 7 7 8 8 9 9 10 11

Output:

5 6 7 8 9 10 11

## Remove Repeated Elements from a Sorted Singly Linked List

### 1)Solution

Since the list is already sorted, all related elements will be grouped together, i.e. if element with value 3 is repeated, all instances of element with value 3 will be grouped together, i.e.

5 6 6 7 7 7 8 9 9 10 11

As a result, we just need to determine if there are more than two adjacent nodes with the same contents.
If yes, remove the node and proceed.

### 2)Algorithm

Traverse the entire linked list, keeping track of the most recently visited Node.
During the traversal, when visiting each node, compare its contents to the last node’s content.
If the data matches

• then delete the current node and proceed to the next node.

If the data does not fit

• simply update the last visited node pointer to point to the current node.
• Then proceed to the next node.

### 3)Implementation

Below is the implementation:

#include <iostream>
using namespace std;
/*
Node will have an int variable as its value as well as a
node pointer(link) to the next Node.
*/
struct node {
int value;
node(int intval)
{
value = intval;
}
};

node* current_node)
{
node* lastNode = NULL;
while (current_node) {
// The new node, i.e. current node, has the same
// value as the previous node.
if (lastNode
&& lastNode->value == current_node->value) {
/* Yes, the new node, i.e. current node, has the
same value as the previous node. Keep the current
node, current node, in a temporary pointer so
that we can erase it later.*/
node* nodeToBeDeleted = current_node;
/*  Let the last node's next pointer point to
the current node's next this will delete the
Current entity from the linked list.*/
// Delete the previously saved temporary node
// pointer.
delete nodeToBeDeleted;
// changing lastnode to cuurent node
continue;
}
else {
/*There is no current node, i.e. the value of
current node does not match the value of the
previous node. Lastnode should be changed to
current node
*/

lastNode = current_node;
// make the currentnode to point to next node
}
}
}
/*
Iterate through the passed array one by one, creating a
node for each element and appending it to the last node's
next pointer. Keep track of the last node generated during
iteration in order to update its next pointer in the next
iteration. Also, save the first node generated, which will
be returned as the root node at the end.
*/
node* createList(int* pointer, int sizeArr)
{
node* nodePointer = NULL;
node* rootNodePointer = NULL;
node* lastNodePointer = NULL;
for (int i = 0; i < sizeArr; i++) {
if (!nodePointer) {
nodePointer = new node(*(pointer + i));
if (!rootNodePointer)
rootNodePointer = nodePointer;
if (lastNodePointer)
}
lastNodePointer = nodePointer;
}
return rootNodePointer;
}
/*
As a temp variable, save the next pointer of the passed
node. Remove the current pointer and transfer the previously
saved next pointer to the destroyList feature.

If ptr is null, it means the linked list has reached its
end  simply return since the entire linked list has been
removed.
*/
{
if (pointer) {
delete pointer;
}
}
/*
Iterate through all nodes,
displaying the content of each node until the linked list
reaches its end.
*/
{
while (pointer != NULL) {
cout << pointer->value << " ";
}
cout << endl;
}
int main()
{
int intarray[]
= { 5, 5, 6, 6, 7, 7, 7, 8, 8, 9, 9, 10, 11 };
node* pointer = createList(intarray, sizeof(intarray)
/ sizeof(int));
}
5 5 6 6 7 7 7 8 8 9 9 10 11
5 6 7 8 9 10 11