এই সমস্যায়, আমাদের N আকারের একটি লিঙ্কযুক্ত তালিকা দেওয়া হয়েছে। আমাদের কাজ হল লিঙ্ক করা তালিকায় পুনরাবৃত্তি না হওয়া খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা .
লিঙ্ক করা তালিকা হল ডেটা স্ট্রাকচারের একটি ক্রম, যা লিঙ্কের মাধ্যমে একসাথে সংযুক্ত থাকে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
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.
সমাধান পদ্ধতি
সমস্যা সমাধানের একটি পদ্ধতি হল একটি হ্যাশ টেবিল তৈরি করা যা উপাদান এবং তাদের সংঘটন ফ্রিকোয়েন্সি সংরক্ষণ করবে। লিঙ্ক করা তালিকায় প্রথম অ-পুনরাবৃত্ত মান খুঁজে পেতে, আমরা লিঙ্কযুক্ত তালিকাটি অতিক্রম করব এবং প্রাথমিক সংঘটন ফ্রিকোয়েন্সি 1 সহ হ্যাশ ম্যাপে উপস্থিত না থাকা উপাদানগুলি সন্নিবেশ করব। হ্যাশ মানচিত্রে কোনও উপাদান উপস্থিত থাকলে তার উপস্থিতি বৃদ্ধি করুন। ফ্রিকোয়েন্সি লিঙ্ক করা তালিকাটি অতিক্রম করার পরে, আমরা হ্যাশ ম্যাপে সেই মানটি পরীক্ষা করব যার সংঘটনের ফ্রিকোয়েন্সি এক এবং প্রথম মানগুলি যেটির সম্মুখীন হয়েছে তা ফিরিয়ে দেব৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#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
