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

}

}

}

Subscribe to:
Post Comments (Atom)

## 7 comments:

Any other solution in O(n) time complexity ?

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

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

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

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

Post a Comment