C++ में क्रमबद्ध लिंक्ड लिस्ट में मेडियन खोजना

समस्या विवरण

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

क्रमबद्ध लिंक्ड लिस्ट एक साधारण लिंक्ड लिस्ट है जिसमें सभी तत्व एक विशिष्ट क्रम में क्रमबद्ध होते हैं। उदाहरण: 4 → 6 → 7 → 9 → NULL

मेडियन लिंक्ड लिस्ट का मध्य तत्व है। इसे इस प्रकार खोजा जा सकता है: - यदि N विषम है: मेडियन (N/2)वां तत्व है - यदि N सम है: मेडियन (N/2)वें और (N/2 + 1)वें तत्व का औसत है

उदाहरण

इनपुट: 2 → 3 → 4 → 6 → 9 → NULL
आउटपुट: 4

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

विधि 1: दो पास (O(N) समय, O(1) स्पेस)

समस्या का एक सरल समाधान लिंक्ड लिस्ट को पार करके सभी तत्वों को गिनना है। अब, यदि गिनती विषम है, तो हम फिर से लिंक्ड लिस्ट को N/2वें तत्व तक पार करेंगे। यदि गिनती सम है, तो हम N/2वें और N/2 + 1वें तत्व तक पार करेंगे, उन्हें जोड़ेंगे और 2 से विभाजित करेंगे।

विधि 2: दो पॉइंटर / धीमा-तेज (O(N) समय, O(1) स्पेस, सिंगल पास)

समस्या को हल करने का एक अन्य दृष्टिकोण दो पॉइंटर पार का उपयोग करके लिंक्ड लिस्ट को पार करना और लिंक्ड लिस्ट के तत्वों की गिनती खोजना है।

यहां तत्वों की गिनती किए बिना मेडियन खोजने का एक एल्गोरिदम है। दो पॉइंटर ptr1 और ptr2 हैं, शर्त के आधार पर, हमारे पास हो सकता है:

• यदि ptr1 NULL नहीं है, तो ptr2 मेडियन है।
• यदि ptr1 NULL है, तो (ptr2 के पिछले नोड + ptr2->data) / 2।

C++ कार्यान्वयन (दो पॉइंटर)

#include <bits/stdc++.h> 
using namespace std; 

struct Node {
    int data;
    struct Node* next;
};

void findMedianValue(Node* head) {
    Node* slow = head;
    Node* fast = head;
    Node* prev = head;
    
    if (head != NULL) {
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        }
        
        if (fast != NULL) {
            // विषम लंबाई: slow मध्य पर है
            cout << slow->data;
        } else {
            // सम लंबाई: slow और prev मध्य के दो तत्व हैं
            cout << float(slow->data + prev->data) / 2;
        }
    }
}

void pushVal(struct Node** head_ref, int new_data) {
    Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main() {
    struct Node* head = NULL;
    pushVal(&head, 3);
    pushVal(&head, 5);
    pushVal(&head, 6);
    pushVal(&head, 8);
    pushVal(&head, 9);
    pushVal(&head, 11);
    cout << "लिंक्ड लिस्ट का मेडियन है ";
    findMedianValue(head);
    return 0;
}

आउटपुट

लिंक्ड लिस्ट का मेडियन है 7

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

• समय जटिलता: O(N) - सिंगल पास
• स्पेस जटिलता: O(1)

धीमा-तेज पॉइंटर कैसे काम करता है

तेज पॉइंटर दो चाल चलता है जबकि धीमा एक चाल चलता है। जब तेज अंत तक पहुंचता है, तो धीमा मध्य पर होता है। विषम लंबाई के लिए, तेज अंतिम नोड पर रुकता है (NULL नहीं)। सम लंबाई के लिए, तेज NULL हो जाता है।