एक लिंक्ड सूची एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड में दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरे ब्लॉक में अगले फ़ील्ड का पता होता है।
आइए मान लें कि हमारे पास एक लिंक्ड सूची है जैसे कि प्रत्येक नोड में एक यादृच्छिक सूचक होता है जो सूची में अन्य नोड्स को इंगित कर रहा है। कार्य उस नोड को खोजना है जिस पर दो लिंक की गई सूचियाँ एक दूसरे को काटती हैं। यदि वे प्रतिच्छेद नहीं करते हैं, तो आउटपुट के रूप में NULL या खाली लौटाएं।
उदाहरण के लिए
इनपुट-1:
<मजबूत> 
आउटपुट:
2
स्पष्टीकरण: चूंकि दी गई लिंक की गई सूची नोड पर '2' मान के साथ प्रतिच्छेद करती है, इसलिए हम '2' मान को आउटपुट के रूप में वापस कर देंगे।
इनपुट-2:
<मजबूत> 
आउटपुट:
NULL
स्पष्टीकरण: चूंकि कोई सामान्य बिंदु नहीं हैं, इसलिए हम इस मामले में NULL वापस कर देंगे।
इस समस्या को हल करने का तरीका
हमारे पास दो लिंक्ड सूचियां हैं जिनमें एक सामान्य बिंदु है जहां वे एक दूसरे को काटते हैं। प्रतिच्छेदन बिंदु खोजने के लिए, हम दोनों लिंक की गई सूचियों को तब तक पार करेंगे जब तक हम यह नहीं पाते कि वे समान रूप से समान मान की ओर इशारा कर रही हैं। किसी बिंदु पर, लिंक की गई सूची के अगले नोड का सूचक समान होगा। इस प्रकार हम उस बिंदु का मान वापस कर देंगे।
- डेटा और पॉइंटर वाली दो लिंक की गई सूचियों को अगले नोड पर ले जाएं।
- एक फंक्शन कॉमनपॉइंट (लिस्टनोड*हेडए, लिस्टनोड*हेडबी) क्रमशः लिंक्ड लिस्ट के दो पॉइंटर्स लेता है और लिंक्ड लिस्ट के कॉमन या इंटरसेक्शन पॉइंट का मान लौटाता है।
- एक पूर्णांक फ़ंक्शन जो लिंक की गई सूची की लंबाई का पता लगाता है, सूची के शीर्ष से दोनों लिंक की गई सूचियों की लंबाई लौटाएगा।
- अब दोनों सूचियों के शीर्ष पर एक पॉइंटर बनाएं और उस सूची को पार करें जो इसकी लंबाई में (पहली सूची की लंबाई - दूसरी सूची की लंबाई) तक अधिक है।
- अब सूची को तब तक देखें जब तक हमें अगला पॉइंटर बराबर न मिल जाए।
- उस विशेष नोड का मान लौटाएं जहां दोनों सूचियां प्रतिच्छेद करती हैं।
उदाहरण
public class Solution {
static listnode headA,
headB;
static class listnode {
int data;
listnode next;
listnode(int d) {
data = d;
next = null;
}
}
int count(listnode head) {
int c = 0;
while (head != null) {
c++;
head = head.next;
}
return c;
}
int commonPoint(listnode headA, listnode headB) {
listnode p1 = headA;
listnode p2 = headB;
int c1 = count(headA);
int c2 = count(headB);
if (c1 > c2) {
for (int i = 0; i < c1 - c2; i++) {
if (p1 == null) {
return - 1;
}
p1 = p1.next;
}
}
if (c1 < c2) {
for (int i = 0; i < c2 - c1; i++) {
if (p2 == null) {
return - 1;
}
p2 = p2.next;
}
}
while (p1 != null && p2 != null) {
if (p1.data == p2.data) {
return p1.data;
}
p1 = p1.next;
p2 = p2.next;
}
return - 1;
}
public static void main(String[] args) {
Solution list = new Solution();
list.headA = new listnode(5);
list.headA.next = new listnode(4);
list.headA.next.next = new listnode(9);
list.headA.next.next.next = new listnode(7);
list.headA.next.next.next.next = new listnode(1);
list.headB = new listnode(6);
list.headB.next = new listnode(7);
list.headB.next.next = new listnode(1);
System.out.println(list.commonPoint(headA, headB));
}
} उपरोक्त कोड को चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
7
स्पष्टीकरण :दी गई लिंक्ड सूचियां 7 पर प्रतिच्छेद कर रही हैं।
