**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.

*Related*