Write a function that deletes duplicates nodes from a list?

INPUT: 12->11->12->21->41->43->21 
OUTPUT: 12->11->21->sorted41->43.

The algorithm is simple -

  • Traverse the list from the head (or start) node. While traversing, compare each node with its next node.
  • If the data of the next node is the same as the current node then delete the next node.
  • Before we delete a node, we need to store the next pointer of the node.

Most of this is done by traversing and checking by the current and current-next variables in the linked list.

Psuedo Code:-

void removeDuplicates(Node* head) 
    /* Pointer to traverse the linked list */
    Node* current = head; 
    /* Pointer to store the next pointer of a node to be deleted*/
    Node* next_next; 
    /* do nothing if the list is empty */
    if (current == NULL) 
    /* 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; 
    else /* This is tricky: only advance if no deletion */
        current = current->next;