Remove duplicates from linked list

© 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