Saturday, May 26, 2007

Write a C program to remove duplicates from a sorted linked list.

As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There's a tricky case where the node after the next node needs to be noted before the deletion.


// Remove duplicates from a sorted list
void RemoveDuplicates(struct node* head)
{
struct node* current = head;
if (current == NULL) return; // do nothing if the list is empty

// Compare current node with next node
while(current->next!=NULL)
{
if (current->data == current->next->data)
{
struct node* nextNext = current->next->next;
free(current->next);
current->next = nextNext;
}
else
{
current = current->next; // only advance if no deletion
}
}
}

7 comments:

Ayman said...

Any other solution in O(n) time complexity ?

manikanta said...

this will work only for the list 1 2 3 3 4 5 like this but it wont work if the duplicate elements r not consecutive like 1 2 3 2 2

Ravi said...

@manikanta: check the title once. It is remove duplicates from "sorted" linked list

himanshu said...
This comment has been removed by the author.
himanshu said...
This comment has been removed by the author.
Anonymous said...

Will it work if its 1 2 2 2 2 2 4 6 8 ?

Namita Agrawal said...

All Government jobs Banks , PSU,CPSU,PSC,UPSC,Defence, Exam,Admit cards,India & Others

All Government jobs Banks , PSU,CPSU,PSC,UPSC,Defence & Others or Submit & verify Email for Latest Jobs Alerts

All Examinations Latest updates or Submit & verify Email for Latest Exams Alerts

Examination Planning & strategy or Submit & verify Email for Latest Exam Plan Alerts

Check your Exam results or Submit & verify Email for Latest Exam Results Alerts

Downloads Your Admit card / Hall Ticket or Submit & verify Email for Latest Admit Cards Alerts