Sıralanmış əlaqəli siyahıda olan bütün dublikatları silin

Sıralanmış əlaqəli siyahı verilmişdir. Sıralanmış əlaqəli siyahıda mövcud olan bütün dublikatları silməli və yeni əlaqəli siyahını göstərməliyik.

Burada nömrənin əlaqəli siyahıda bir neçə dəfə baş verməsi halında təkrarlanan adlanır.

misal

Giriş: 982 -> 982 -> 982 -> 982 -> 716 -> 211 -> 211 -> 162 -> 115 -> 115 -> 73 -> 73 -> 49 -> 49
Çıxış: 982 -> 716 -> 211 -> 162 -> 115 -> 73 -> 49 -> XNUMX

Bu metodda, əlaqəli siyahıdan keçərkən, indiki qovşağın elementi növbəti qovşaqla eynidirsə, qovluğu siləcəyik.
Zaman Mürəkkəbliyi: O (n), burada n əlaqəli siyahıda qovşaq sayıdır

Alqoritm

  1. İki göstərici yaradın temp, curr. curr göstəricisi ağacdan keçmək və temp düyünün növbəti göstəricisini saxlamaqdır.
  2. Bağlı siyahıdan keçərkən, indiki düyündəki element növbəti düyünə bərabərdirsə, düyünü silin və curr növbəti göstəricini sonrakıya keçin.
  3. Əgər bərabər deyilsə, onda cərəyan göstəricisini hərəkət etdirin, yəni həmin elementlə artıq təkrarlanan qovşaq yoxdur, buna görə növbəti elementə, yəni curr = curr-> next

C ++ Proqramı

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

Şərh yaz

Translate »