Remove all duplicates in a sorted linked list

Given a sorted linked list. We have to remove all the duplicates that are present in the sorted linked list and display the new linked list.

Here, the number is called duplicate if the number has occured multiple times in the linked list.

Example

Input : 982 ->982 ->982 ->982 ->716 ->211 ->211 ->162 ->115 ->115 ->73 ->73 ->49 ->49
Output : 982 ->716 ->211 ->162 ->115 ->73 ->49

In this method, while traversing the linked list, we will delete the node, if the element of the present node is same as the next node.
Time Complexity: O(n), where n is the number of nodes in the linked list

Algorithm

  1. Create two pointers temp, curr. curr pointer is to traverse the tree and the temp is to store the next pointer of the node.
  2. While traversing the linked list, if the element in the present node is equal to the next node, then delete the node and move the curr next pointer to next of next.
  3. If not equal, then move the curr pointer ie, no more duplicate nodes are present with that element, so going to the next element ie, curr = curr->next

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LL{
	int data;
	LL *next;	
};

void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL*temp=*head,*curr=new LL;
			curr->data=dataToBeInserted;
			curr->next=NULL;
	if(*head==NULL)
			*head=curr;
		
	else
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}

void removeDuplicatesSorted(struct LL ** head)
{
    
    struct LL* curr = *head , * temp; 
   
    if (curr == NULL) 
       return; 
 
    while (curr->next != NULL)  //Traverse till end
    {
       if (curr->data == curr->next->data)  //if data is same then advance the pointer to next of next
       {            
           temp = curr->next->next;
           delete(curr->next);
           curr->next = temp;  
       }
       else  //move ahead if data is not equal
          curr = curr->next; 
    }
	
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<data<<" ->";
			else
			cout<data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,73);
	insertAtBeginning(&head,73);
	insertAtBeginning(&head,115);
	insertAtBeginning(&head,115);
	insertAtBeginning(&head,115);
	insertAtBeginning(&head,115);
	insertAtBeginning(&head,162);
	insertAtBeginning(&head,211);
	insertAtBeginning(&head,211);
	insertAtBeginning(&head,211);
	insertAtBeginning(&head,211);
	insertAtBeginning(&head,211);
	insertAtBeginning(&head,716);
	insertAtBeginning(&head,982); 
	insertAtBeginning(&head,982);
	insertAtBeginning(&head,982);
	insertAtBeginning(&head,982);
	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	
	removeDuplicatesSorted(&head);
	
	cout<<"\nAfter removing duplicates from sorted given list the list becomes :-\n";
	display(&head);
	
	return 0;
}

Translate ยป