Remove all the duplicates from a sorted linked list


Given a sorted linked list, remove all the duplicates from the list. For example, given 1->2->3->3->6, return 1->2->6. Another example, given 1->1->1->2->4, return 2->4.

typedef struct node Node;

/* The function removes duplicates from a sorted list */
void removeDuplicates(Node** head)
{ 
  /* do nothing if the list is empty */
  Node* current = *head;  
  if(current == NULL)
     return;

  /* Pointer to traverse the linked list */
  Node* pre_head = (Node*) malloc(sizeof(Node));
  pre_head->next = *head;

  /* Pointer to store the next pointer of a node to be deleted*/
  Node* next_next;
  Node* pre = pre_head;
  bool deleted = false;
 
  /* Traverse the list till last node */
  while(current->next != NULL)
  {
   /* Compare current node with next node */
    if(current->data == current->next->data) {       
		/*The sequence of steps is important*/              
		next_next = current->next->next;
		free(current->next);
		current->next = next_next;
		deleted = true;
    }
    else if (deleted)  {
		pre->next = current->next;
		free(current);
		current = pre->next;
		deleted = false;
    }
	else {
		pre = current;
		current = current->next;
    }
  }

  /* remove the last duplicated node*/
  if (deleted) {
	  pre->next = NULL;
	  free(current);
  }
  
  *head = pre_head->next;
  free(pre_head);
}
 

To test the code, please use the testing program from http://www.geeksforgeeks.org/remove-duplicates-from-a-sorted-linked-list/.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s