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

3 comments:

Anonymous said...

But what if the duplicate node is not adjacent? I mean when 1st and last node contains the same data...

Kiran Patil said...

then its not called sorted list lol

Anonymous said...

I know this web page offers quality dependent
articles and additional stuff, is there any other web page which gives such
stuff in quality?

my website :: filing bankruptcy in florida