© Parineeth M R

** 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++

/* head: first node in the linked list */ void remove_duplicates(struct node *head) { struct node *cur_node, *iter_node, *prev_node; /*If there are 0 or 1 nodes in linked list, then simply return*/ if (head == NULL || head->next == NULL) return; cur_node = head; 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

/* head: first node in the linked list */ public static void removeDuplicates(LinkedListNode head) { /*If there are 0 or 1 nodes in linked list, then simply return*/ if (head == null || head.next == null) return; LinkedListNode curNode = head; while (curNode != null) { /*Iterate from node after curNode to the end of linked list*/ LinkedListNode iterNode = curNode.next; LinkedListNode prevNode = curNode; 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

#head: first node in the linked list @staticmethod def remove_duplicates(head): #If there are 0 or 1 nodes in linked list, then simply return if (not head or not head.next): return cur_node = head 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