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
}
}
}
Any other solution in O(n) time complexity ?
ReplyDeletethis 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
ReplyDelete@manikanta: check the title once. It is remove duplicates from "sorted" linked list
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteWill it work if its 1 2 2 2 2 2 4 6 8 ?
ReplyDelete