एक लिंक्ड सूची एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड में दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरे ब्लॉक में अगले फ़ील्ड का पता होता है।
आइए मान लें कि हमारे पास एक लिंक्ड सूची है जैसे कि प्रत्येक नोड में एक यादृच्छिक सूचक होता है जो सूची में अन्य नोड्स को इंगित कर रहा है। कार्य उस नोड को खोजना है जिस पर दो लिंक की गई सूचियाँ एक दूसरे को काटती हैं। यदि वे प्रतिच्छेद नहीं करते हैं, तो आउटपुट के रूप में NULL या खाली लौटाएं।
उदाहरण के लिए
इनपुट-1:
<मजबूत> 
आउटपुट:
2
स्पष्टीकरण: चूंकि दी गई लिंक की गई सूची नोड पर '2' मान के साथ प्रतिच्छेद करती है, इसलिए हम '2' मान को आउटपुट के रूप में वापस कर देंगे।
इनपुट-2:
<मजबूत> 
आउटपुट:
NULL
स्पष्टीकरण: चूंकि कोई सामान्य बिंदु नहीं हैं, इसलिए हम इस मामले में NULL वापस कर देंगे।
इस समस्या को हल करने का तरीका
हमारे पास दो लिंक्ड सूचियां हैं जिनमें एक सामान्य बिंदु है जहां वे एक दूसरे को काटते हैं। प्रतिच्छेदन बिंदु खोजने के लिए, हम दोनों लिंक की गई सूचियों को तब तक पार करेंगे जब तक हम यह नहीं पाते कि वे समान रूप से समान मान की ओर इशारा कर रही हैं। किसी बिंदु पर, लिंक की गई सूची के अगले नोड का सूचक समान होगा। इस प्रकार हम उस बिंदु का मान वापस कर देंगे।
- डेटा और पॉइंटर वाली दो लिंक की गई सूचियों को अगले नोड पर ले जाएं।
- एक फंक्शन कॉमनपॉइंट (लिस्टनोड*हेडए, लिस्टनोड*हेडबी) क्रमशः लिंक्ड लिस्ट के दो पॉइंटर्स लेता है और लिंक्ड लिस्ट के कॉमन या इंटरसेक्शन पॉइंट का मान लौटाता है।
- एक पूर्णांक फ़ंक्शन जो लिंक की गई सूची की लंबाई का पता लगाता है, सूची के शीर्ष से दोनों लिंक की गई सूचियों की लंबाई लौटाएगा।
- अब दोनों सूचियों के शीर्ष पर एक पॉइंटर बनाएं और उस सूची को पार करें जो इसकी लंबाई में (पहली सूची की लंबाई - दूसरी सूची की लंबाई) तक अधिक है।
- अब सूची को तब तक देखें जब तक हमें अगला पॉइंटर बराबर न मिल जाए।
- उस विशेष नोड का मान लौटाएं जहां दोनों सूचियां प्रतिच्छेद करती हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class listnode {
public:
int data;
listnode * next;
};
// Find the length of the linked list
int count(listnode * head) {
int count = 0;
while (head != NULL) {
count++;
head = head -> next;
}
return count;
}
//Function to get the common point of two linked list
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
स्पष्टीकरण: दी गई लिंक्ड सूचियां '7' पर मर्ज हो रही हैं।
