এই সমস্যাতে, আমাদের একটি লিংকড লিস্ট LL দেওয়া আছে যার সাইজ N। আমাদের কাজ হল লিংকড লিস্টে প্রথম নন-রিপিটিং এলিমেন্ট বের করার প্রোগ্রাম তৈরি করা।
লিংকড লিস্ট হল ডেটা স্ট্রাকচারের একটি ক্রম যা লিংক দিয়ে একসাথে জড়িত থাকে।
উদাহরণ দেখি:
ইনপুট: LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5 আউটপুট: 1
ব্যাখ্যা -
একবার থাকা এলিমেন্টগুলো হল 1 এবং 6। এর মধ্যে 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
