Remove duplicates from a sorted linked list.
void remove_dups_sorted(node_t *head)
{
node_t *cur = head;
while (cur && cur->next) {
if (cur->val == cur->next->val) {
node_t *dup = cur->next;
cur->next = dup->next;
free(dup); /* do not advance: next may also be a duplicate */
} else {
cur = cur->next;
}
}
}
Points: in a sorted list duplicates are adjacent: one pass, O(1) space. For an unsorted list, use a hash set or bitmap of seen values (O(n)) or nested loops (O(n²) without extra memory).