வரிசைப்படுத்தப்பட்ட இணைக்கப்பட்ட பட்டியலில் உள்ள அனைத்து நகல்களையும் அகற்று


வரிசைப்படுத்தப்பட்ட இணைக்கப்பட்ட பட்டியல் கொடுக்கப்பட்டுள்ளது. வரிசைப்படுத்தப்பட்ட இணைக்கப்பட்ட பட்டியலில் உள்ள அனைத்து நகல்களையும் அகற்றி, புதிய இணைக்கப்பட்ட பட்டியலைக் காண்பிக்க வேண்டும்.

இங்கே, இணைக்கப்பட்ட பட்டியலில் எண் பல முறை நிகழ்ந்திருந்தால் அந்த எண் நகல் என்று அழைக்கப்படுகிறது.

உதாரணமாக

உள்ளீடு: 982 -> 982 -> 982 -> 982 -> 716 -> 211 -> 211 -> 162 -> 115 -> 115 -> 73 -> 73 -> 49 -> 49
வெளியீடு: 982 -> 716 -> 211 -> 162 -> 115 -> 73 -> 49

இந்த முறையில், இணைக்கப்பட்ட பட்டியலைக் கடந்து செல்லும்போது, ​​தற்போதைய முனையின் உறுப்பு அடுத்த முனைக்கு சமமாக இருந்தால், முனையை நீக்குவோம்.
நேர சிக்கலானது: O (n), இங்கு n என்பது இணைக்கப்பட்ட பட்டியலில் உள்ள முனைகளின் எண்ணிக்கை

அல்காரிதம்

  1. இரண்டு சுட்டிகள் தற்காலிகமாக உருவாக்கவும். கர்ர் சுட்டிக்காட்டி என்பது மரத்தை கடந்து செல்வதும், முனையின் அடுத்த சுட்டிக்காட்டி சேமிப்பதும் ஆகும்.
  2. இணைக்கப்பட்ட பட்டியலில் பயணிக்கும்போது, ​​தற்போதைய முனையிலுள்ள உறுப்பு அடுத்த முனைக்கு சமமாக இருந்தால், முனையை நீக்கி, கர்ர் அடுத்த சுட்டிக்காட்டி அடுத்த இடத்திற்கு நகர்த்தவும்.
  3. சமமாக இல்லாவிட்டால், கர்ர் சுட்டிக்காட்டி நகர்த்தவும், அதாவது அந்த உறுப்புடன் மேலும் நகல் முனைகள் இல்லை, எனவே அடுத்த உறுப்புக்குச் செல்லுங்கள், அதாவது curr = curr-> next

சி ++ திட்டம்

#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;
}