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;
}