एक लिंक्ड सूची एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड के दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरे ब्लॉक में अगले फील्ड का पता होता है।
आइए मान लें कि हमारे पास एक लिंक्ड सूची है जैसे कि प्रत्येक नोड में एक रैंडम पॉइंटर होता है जो सूची में अन्य नोड्स की ओर इशारा करता है। कार्य उस नोड को खोजना है जिस पर दो लिंक्ड सूचियाँ एक दूसरे को काटती हैं। यदि वे इंटरसेक्ट नहीं करते हैं, तो आउटपुट के रूप में NULL या खाली वापस करें।
उदाहरण के लिए
इनपुट-1:
आउटपुट:
2
व्याख्या: चूंकि दी गई लिंक्ड सूची मान '2' वाले नोड पर इंटरसेक्ट होती है, हम मान '2' को आउटपुट के रूप में वापस करेंगे।
इनपुट-2:
आउटपुट:
NULL
व्याख्या: चूंकि कोई सामान्य बिंदु नहीं हैं, हम इस मामले में NULL वापस करेंगे।
इस समस्या को हल करने का दृष्टिकोण
हमारे पास दो लिंक्ड सूचियाँ हैं जिनका एक सामान्य बिंदु है जहां वे एक दूसरे को काटती हैं। इंटरसेक्शन पॉइंट खोजने के लिए, हम दोनों लिंक्ड सूचियों को तब तक पार करेंगे जब तक हम यह नहीं पाते कि वे समान रूप से उसी मान की ओर इशारा कर रहे हैं। किसी बिंदु पर, लिंक्ड सूची के अगले नोड का पॉइंटर समान होगा। इस प्रकार हम उस बिंदु का मान वापस करेंगे जहां दोनों सूचियाँ इंटरसेक्ट होती हैं।
- डेटा और अगले नोड के पॉइंटर के साथ दो लिंक्ड सूचियाँ लें।
- commonPoint(listnode*headA, listnode*headB) फंक्शन लिंक्ड सूची के दो पॉइंटर्स को क्रमशः लेता है और लिंक्ड सूची के सामान्य या इंटरसेक्शन पॉइंट का मान वापस करता है।
- एक पूर्णांक फंक्शन जो लिंक्ड सूची की लंबाई खोजता है, सूची के हेड से दोनों लिंक्ड सूचियों की लंबाई वापस करेगा।
- अब दोनों सूचियों के हेड के पॉइंटर बनाएं और उस सूची को पार करें जो लंबाई में अधिक है जब तक (पहली सूची की लंबाई - दूसरी सूची की लंबाई)।
- अब सूची को तब तक पार करें जब तक हम अगले पॉइंटर को समान नहीं पाते।
- उस विशेष नोड का मान वापस करें जहां दोनों सूचियाँ इंटरसेक्ट होती हैं।
उदाहरण
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 पर इंटरसेक्ट हो रही हैं।
