*1.6K*

Question:Given a sorted Linked List. Write a program to remove all the duplicates.

Input:4 -> 8 -> 8 -> 8 -> 15 -> 16 -> 23 -> 23 -> 42.

Output:4 -> 8 -> 15 -> 16 -> 23 -> 42

In a sorted Linked List, all the node that are duplicate will be together. To remove duplicates we need to traverse the linked list and if two adjacent nodes have same value, remove one of them. If adjacent node have different value then move forward.

// function to remove the duplicates from a sorted Linked List struct node * removeDuplicatesSorted(struct node * head) { struct node * traveller = head; struct node * temp; while(traveller) { // we need to keep removing the elements till duplicates are found while(traveller -> next) { if(traveller -> data == traveller -> next -> data) { // We need to remove the next node // Assign the next node to a temp temp = traveller -> next; // Assign the next of current node to the next of adjacent node traveller -> next = temp -> next; // Free the temp free(temp); } else break; } // move to the next node traveller = traveller -> next; } return head; }

*Time Complexity:-* O(n), since we need to traverse the entire list

*Space Complexity:-* O(1), only one extra space is used.