QUESTION

Write a removeDuplicates() function which takes a list sorted in non-decreasing order and deletes any duplicate nodes from the list. The list should only be traversed once.\n\nFor example if the linked list is 11->11->11->21->43->43->60 then removeDuplicates() should convert the list to 11->21->43->60.

“TESTCASE_1”: “5\n5 4 4 3 2\n###—###SEPERATOR—###—\n5 4 3 2”, “TESTCASE_2”: “6 \n1 1 1 5 6 9\n###—###SEPERATOR—###—\n1 5 6 9”, “TESTCASE_3”: “4\n2 1 3 3\n###—###SEPERATOR—###—\n2 1 3”, “TESTCASE_4”: “7\n1 2 2 3 3 4 5\n###—###SEPERATOR—###—\n1 2 3 4 5”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

/* C Program to remove duplicates from a sorted linked list */
#include<stdio.h>
#include<stdlib.h>
 
/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};
 
/* The function removes duplicates from a sorted list */
void removeDuplicates(struct Node* head)
{
    /* Pointer to traverse the linked list */
    struct Node* current = head;
 
    /* Pointer to store the next pointer of a node to be deleted*/
    struct Node* next_next; 
   
    /* do nothing if the list is empty */
    if (current == NULL) 
       return; 
 
    /* 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;  
       }
       else /* This is tricky: only advance if no deletion */
       {
          current = current->next; 
       }
    }
}
 
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the linked list */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));
             
    /* put in the data  */
    new_node->data  = new_data;
                 
    /* link the old list off the new node */
    new_node->next = (*head_ref);     
         
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
 
/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
    while (node!=NULL)
    {
       printf("%d ", node->data);
       node = node->next;
    }
} 
 
/* Drier program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  int i,n;
  scanf("%d",&n);
  int arr[n];
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
  for(i=n-1;i>=0;i--)
    push(&head,arr[i]);
   
    /* Let us create a sorted linked list to test the functions
     Created linked list will be 11->11->11->13->13->20 */
                                 
 
    
 
    /* Remove duplicates from linked list */
    removeDuplicates(head); 
 
            
    printList(head);            
   
    return 0;
}