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