इस समस्या में, हमें N आकार की एक लिंक की गई सूची LL दी जाती है। हमारा कार्य लिंक्ड सूची में गैर-दोहराव खोजने के लिए एक प्रोग्राम बनाना है। ।
लिंक्ड सूची डेटा संरचनाओं का एक क्रम है, जो लिंक के माध्यम से एक साथ जुड़े होते हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input: LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5 Output: 1
स्पष्टीकरण -
The elements with a single occurrence frequency are 1 and 6. Out of these 1 occurred first in the linked list.
समाधान दृष्टिकोण
समस्या को हल करने का एक तरीका हैश टेबल बनाना है जो तत्वों और उनकी घटना आवृत्ति को संग्रहीत करेगा। लिंक की गई सूची में पहले गैर-दोहराए जाने वाले मान को खोजने के लिए, हम लिंक की गई सूची को पार करेंगे और उन तत्वों को सम्मिलित करेंगे जो हैश मैप में मौजूद नहीं हैं, प्रारंभिक आवृत्ति आवृत्ति के साथ। यदि कोई तत्व हैश मैप में मौजूद है तो इसकी घटना को बढ़ाएं आवृत्ति। लिंक की गई सूची का पता लगाने के बाद, हम हैश मैप में उस मान की जांच करेंगे जिसकी आवृत्ति आवृत्ति एक है और पहले मान का सामना करना पड़ा है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int findFirstNonRepLL(struct Node *head){
unordered_map<int, int> freqMap;
for (Node *temp=head; temp!=NULL; temp=temp->next){
freqMap[temp->data]++;
}
for (Node *temp=head; temp!=NULL; temp=temp->next){
if (freqMap[temp->data] == 1){
return temp->data;
}
}
return -1;
}
int main(){
struct Node* head = NULL;
push(&head, 5);
push(&head, 6);
push(&head, 2);
push(&head, 1);
push(&head, 4);
push(&head, 2);
push(&head, 6);
push(&head, 4);
cout<<"The first non repeating element of the linked list is "<<findFirstNonRepLL(head);
return 0;
} आउटपुट
The first non repeating element of the linked list is 1