मान लीजिए हमारे पास कुछ तत्वों की एक सूची है। हमें उन सभी तत्वों को हटाना होगा जो एक से अधिक बार घटित हुए हैं। तो सूची में केवल विशिष्ट तत्व ही रहेंगे। तो अगर सूची [1,1,1,2,2,3,5,6,6,7,8] की तरह है, तो आउटपुट [3,5,7,8] होगा, अन्य सभी तत्व मौजूद हैं एक से अधिक बार।
आइए चरणों को देखें -
- मान -1 के साथ एक डमी नोड बनाएं, पिछला:=NULL, dummyPtr:=डमी
- जबकि सिर खाली नहीं है
- यदि शीर्ष का अगला भाग मौजूद है या शीर्ष का मान अगले नोड के मान के समान नहीं है, तो
- dummyPtr के आगे :=head
- अस्थायी:=सिर के बगल में, और सिर के अगले हिस्से को खाली कर दें
- सिर:=अस्थायी
- dummyPtr :=अगला dummyPtr
- अन्यथा
- पिछला:=सिर, और सिर:=सिर के आगे
- जबकि शीर्ष शून्य नहीं है और शीर्ष का मान =पिछला का मान
- पिछला :=सिर और सिर :=सिर के आगे
- यदि शीर्ष का अगला भाग मौजूद है या शीर्ष का मान अगले नोड के मान के समान नहीं है, तो
- डमी का अगला भाग लौटाएं
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(-1);
ListNode* prev = NULL;
ListNode* dummyPtr = dummy;
ListNode* nextNode;
while(head){
if(!head->next || head->val != head->next->val){
dummyPtr->next = head;
ListNode* temp = head->next;
head->next = NULL;
head = temp;
dummyPtr = dummyPtr->next;
} else {
prev = head;
head = head->next;
while(head && head->val == prev->val){
prev = head;
head = head->next;
}
}
}
return dummy->next;
}
};
main(){
Solution ob;
vector<int> v = {1,1,1,2,2,3,5,6,6,7,8};
ListNode *head = make_list(v);
print_list(ob.deleteDuplicates(head));
} इनपुट
[1,1,1,2,2,3,5,6,6,7,8]
आउटपुट
[3, 5, 7, 8, ]