C++ में लिंक्ड लिस्ट में पहला गैर-दोहराव वाला तत्व खोजना

समस्या विवरण

इस समस्या में, हमें आकार N की एक लिंक्ड लिस्ट LL दी गई है। हमारा कार्य लिंक्ड लिस्ट में गैर-दोहराव वाला तत्व खोजने के लिए एक प्रोग्राम बनाना है।

लिंक्ड लिस्ट डेटा संरचनाओं का एक क्रम है, जो लिंक के माध्यम से एक साथ जुड़े होते हैं।

उदाहरण

इनपुट: LL = 4 → 6 → 2 → 4 → 1 → 2 → 6 → 5
आउटपुट: 1

व्याख्या

एकल घटना आवृत्ति वाले तत्व 1 और 5 हैं। इनमें से 1 लिंक्ड लिस्ट में पहले आया।

हल का दृष्टिकोण

समस्या को हल करने का एक दृष्टिकोण एक हैश टेबल बनाना है जो तत्वों और उनकी घटना आवृत्ति को संग्रहीत करेगा। लिंक्ड लिस्ट में पहले गैर-दोहराव वाले मान को खोजने के लिए, हम लिंक्ड लिस्ट को पार करेंगे और उन तत्वों को डालेंगे जो हैश मैप में मौजूद नहीं हैं, उन्हें प्रारंभिक घटना आवृत्ति 1 के साथ डालेंगे। यदि कोई तत्व हैश मैप में मौजूद है तो उसकी घटना आवृत्ति बढ़ाएं। लिंक्ड लिस्ट को पार करने के बाद, हम हैश मैप में उस मान की जांच करेंगे जिसकी घटना आवृत्ति एक है और पहला मान वापस करेंगे जो मिलता है।

C++ कार्यान्वयन

#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 << "लिंक्ड लिस्ट का पहला गैर-दोहराव वाला तत्व है " << findFirstNonRepLL(head);
    return 0;
}

आउटपुट

लिंक्ड लिस्ट का पहला गैर-दोहराव वाला तत्व है 1

जटिलता विश्लेषण

• समय जटिलता: O(N) - दो पास
• स्पेस जटिलता: O(N) - हैश मैप के लिए

वैकल्पिक दृष्टिकोण

यदि मानों की रेंज छोटी है (उदाहरण के लिए 0-1000), तो O(1) स्पेस के लिए हैश मैप के बजाय सरणी का उपयोग करें।