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)

  /* 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;
		current->next = next_next;
		deleted = true;
    else if (deleted)  {
		pre->next = current->next;
		current = pre->next;
		deleted = false;
	else {
		pre = current;
		current = current->next;

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

To test the code, please use the testing program from

Leave a Reply

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

You are commenting using your 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