C++ में दो लिंक्ड लिस्ट का इंटरसेक्शन

लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड के दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरा ब्लॉक अगले फील्ड का पता रखता है।

मान लीजिए हमारे पास एक लिंक्ड लिस्ट है जैसे कि प्रत्येक नोड में एक रैंडम पॉइंटर होता है जो लिस्ट में अन्य नोड्स की ओर इंगित करता है। कार्य उस नोड को ढूंढना है जिस पर दो लिंक्ड लिस्ट एक दूसरे को इंटरसेक्ट करती हैं। यदि वे इंटरसेक्ट नहीं करते हैं, तो आउटपुट के रूप में NULL या खाली लौटाएं।

उदाहरण के लिए

इनपुट-1:

आउटपुट:

व्याख्या: चूंकि दी गई लिंक्ड लिस्ट मान '2' वाले नोड पर इंटरसेक्ट करती है, हम आउटपुट के रूप में मान '2' लौटाएंगे।

इनपुट-2:

आउटपुट:

NULL

व्याख्या: चूंकि कोई सामान्य बिंदु नहीं हैं, हम इस मामले में NULL लौटाएंगे।

इस समस्या को हल करने का दृष्टिकोण

हमारे पास दो लिंक्ड लिस्ट हैं जिनका एक सामान्य बिंदु है जहां वे एक दूसरे को इंटरसेक्ट करती हैं। इंटरसेक्शन बिंदु ढूंढने के लिए, हम दोनों लिंक्ड लिस्ट को तब तक ट्रैवर्स करेंगे जब तक हम यह नहीं पाते कि वे समान मान की ओर इंगित कर रहे हैं। किसी बिंदु पर, लिंक्ड लिस्ट के अगले नोड का पॉइंटर समान होगा। इस प्रकार हम उस बिंदु का मान लौटाएंगे।

डेटा और अगले नोड के पॉइंटर के साथ दो लिंक्ड लिस्ट लें।
एक फ़ंक्शन commonPoint(listnode*headA, listnode*headB) दो लिंक्ड लिस्ट के पॉइंटर्स को क्रमशः लेता है और लिंक्ड लिस्ट के सामान्य या इंटरसेक्शन बिंदु का मान लौटाता है।
एक पूर्णांक फ़ंक्शन जो लिंक्ड लिस्ट की लंबाई ढूंढता है, लिस्ट के हेड से दोनों लिंक्ड लिस्ट की लंबाई लौटाएगा।
अब दोनों लिस्ट के हेड के पॉइंटर बनाएं और उस लिस्ट को ट्रैवर्स करें जो लंबाई में अधिक है जब तक (पहली लिस्ट की लंबाई - दूसरी लिस्ट की लंबाई)।
अब लिस्ट को तब तक ट्रैवर्स करें जब तक हमें अगला पॉइंटर समान न मिल जाए।
उस विशेष नोड का मान लौटाएं जहां दोनों लिस्ट इंटरसेक्ट करती हैं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class listnode {
    public:
        int data;
        listnode * next;
};
// लिंक्ड लिस्ट की लंबाई ढूंढें
int count(listnode * head) {
    int count = 0;
    while (head != NULL) {
        count++;
        head = head -> next;
    }
    return count;
}
// दो लिंक्ड लिस्ट का सामान्य बिंदु प्राप्त करने का फ़ंक्शन
int commonPoint(listnode * headA, listnode * headB) {
    int len1 = count(headA);
    int len2 = count(headB);
    listnode * p1 = headA;
    listnode * p2 = headB;
    if (len1 > len2) {
        for (int i = 0; i < len1 - len2; ++i) {
            p1 = p1 -> next;
        }
    }
    if (len1 < len2) {
        for (int i = 0; i < len2 - len1; ++i) {
            p2 = p2 -> next;
        }
    }
    while (p1 != NULL and p2 != NULL) {
        if (p1 == p2) {
            return p1 -> data;
        }
        p1 = p1 -> next;
        p2 = p2 -> next;
    }
    return -1;
}
int main() {
    listnode * head;
    listnode * headA = new listnode();
    headA -> data = 5;
    listnode * headB = new listnode();
    headB -> data = 4;
    head = new listnode();
    head -> data = 9;
    headB -> next = head;
    head = new listnode();
    head -> data = 2;
    headB -> next -> next = head;
    head = new listnode();
    head -> data = 7;
    headA -> next = head;
    headB -> next -> next -> next = head;
    head = new listnode();
    head -> data = 3;
    headA -> next -> next = head;
    headA -> next -> next -> next = NULL;
    cout << commonPoint(headA, headB) << endl;
}

उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,

आउटपुट

व्याख्या: दी गई लिंक्ड लिस्ट '7' पर मर्ज हो रही हैं।

C++ में दो लिंक्ड लिस्ट का इंटरसेक्शन