# Remove duplicates from linked list

Question 6. Remove duplicates from a linked list

For removing duplicates, we can try two approaches
1. Use brute force. Pick each node (let’s call it current node) in the linked list, then check the nodes that occur after the current node and remove those nodes that are identical to the current node. The time complexity is O(n2). We don’t need additional memory.

2. Use a hash table. As we traverse the linked list, we store the data of the nodes in the hash table. If the data of a node has already been stored in the hash table, then it is a duplicate and we delete the node from the linked list. The time complexity is O(n) but we will use additional memory because of the hash table.
The code for the brute force approach is given below

## C/C++

```
/*
*/
{
struct node *cur_node, *iter_node, *prev_node;

/*If there are 0 or 1 nodes in linked list, then simply return*/
return;

while (cur_node) {
/*Iterate from node after cur_node to the end of the linked list*/
iter_node = cur_node->next;
prev_node = cur_node;

while (iter_node) {
if (cur_node->data == iter_node->data) {
/*iter_node is a duplicate of cur_node. So remove it*/
prev_node->next = iter_node->next;
free(iter_node);
iter_node = prev_node->next;
} else {
prev_node = iter_node;
iter_node = iter_node->next;
}
}

cur_node = cur_node->next;
}
}

```

## Java

```
/*
*/
/*If there are 0 or 1 nodes in linked list, then simply return*/
return;

while (curNode != null) {
/*Iterate from node after curNode to the end of linked list*/

while (iterNode != null) {
if (curNode.data == iterNode.data) {
/*iterNode is a duplicate of curNode.
so remove it*/
prevNode.next = iterNode.next;
iterNode = iterNode.next;
} else {
prevNode = iterNode;
iterNode = iterNode.next;
}
}

curNode = curNode.next;
}
}

```

## Python

```
@staticmethod
#If there are 0 or 1 nodes in linked list, then simply return
return

while (cur_node) :
#Iterate from node after cur_node to the end of the linked list
iter_node = cur_node.next
prev_node = cur_node

while (iter_node) :
if (cur_node.data == iter_node.data) :
#iter_node is a duplicate of cur_node. so
#remove it
prev_node.next = iter_node.next
iter_node = iter_node.next
else :
prev_node = iter_node
iter_node = iter_node.next

cur_node = cur_node.next

```