Remove duplicates from a sorted linked list.

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.