अवधारणा
दिए गए क्रमबद्ध डौबली लिंक्ड लिस्ट के संबंध में जिसमें धनात्मक विशिष्ट तत्व हैं, हमारा कार्य डौबली लिंक्ड लिस्ट में उन जोड़ों को निर्धारित करना है जिनका उत्पाद दिए गए मान x के बराबर है, बिना किसी अतिरिक्त स्थान का उपभोग किए।
इनपुट
सूची = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9 x = 8
आउटपुट
(1, 8), (2, 4)
इनपुट
सूची1 = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 x = 6
आउटपुट
(1, 4), (2,3)
विधि
इस समस्या के लिए एक सरल दृष्टिकोण के अनुसार, हम लिंक्ड लिस्ट को पार करते हुए दो नेस्टेड लूप लागू करते हैं और सभी जोड़ों को निर्धारित करते हैं और उत्पाद x के बराबर वाले जोड़ों की जांच करते हैं। यहां, इस समस्या के लिए समय जटिलता O(n^2) होगी, जहां n डौबली लिंक्ड लिस्ट में नोड्स की कुल संख्या है।
इस समस्या के लिए एक कुशल समाधान चर्चा की गई है। एल्गोरिदम के चरण यहां दिए गए हैं -
हम क्रमबद्ध डौबली लिंक्ड लिस्ट में उम्मीदवार तत्वों को निर्धारित करने के लिए दो पॉइंटर चर प्रारंभ करते हैं।
हम first1 को डौबली लिंक्ड लिस्ट की शुरुआत के साथ प्रारंभ करते हैं यानी first1=head और second1 को डौबली लिंक्ड लिस्ट के अंतिम नोड के साथ प्रारंभ करते हैं यानी second1=last_node।
अब हम पहले और दूसरे पॉइंटर्स को पहले और अंतिम नोड्स के रूप में प्रारंभ करते हैं। इस मामले में हमारे पास रैंडम एक्सेस नहीं है, इसलिए second1 को प्रारंभ करने के लिए सूची को पार करते हैं।
यह देखा गया है कि यदि first1 और second1 का वर्तमान योग x से छोटा है, तो हम first1 को आगे की दिशा में ले जाते हैं। अन्यथा यदि first1 और second1 का वर्तमान योग x से बड़ा है, तो हम second1 को पीछे की दिशा में ले जाते हैं।
अंत में, लूप समाप्ति शर्तें सरणियों से भी अलग हैं। इस मामले में, लूप तब समाप्त होता है जब दोनों पॉइंटर्स में से कोई भी NULL हो जाता है, या वे एक-दूसरे को पार कर जाते हैं (second1->next = first1), या वे समान हो जाते हैं (first1 == second1)।
उदाहरण
// C++ प्रोग्राम एक जोड़ी ढूंढने के लिए जिसका // दिए गए उत्पाद x के बराबर हो क्रमबद्ध डौबली // लिंक्ड लिस्ट में #include <bits/stdc++.h> using namespace std; // डौबली लिंक्ड लिस्ट नोड दिखाता है struct Node1 { int data1; struct Node1 *next1, *prev1; }; // फ़ंक्शन दिखाता है जिसका उत्पाद // दिए गए मान x के बराबर हो void pairProduct(struct Node1* head1, int x1){ // अब दो पॉइंटर्स सेट करें, // पहला DLL की शुरुआत में और दूसरा DLL के अंत में। struct Node1* first1 = head1; struct Node1* second1 = head1; while (second1->next1 != NULL) second1 = second1->next1; // उपयोग किया जाता है यह ट्रैक करने के लिए कि क्या हमें एक जोड़ी मिली या नहीं bool found1 = false; // अब लूप तब समाप्त होता है जब दोनों पॉइंटर्स में से कोई भी // NULL हो जाता है, या वे एक-दूसरे को पार कर जाते हैं (second1->next1 // == first1), या वे समान हो जाते हैं (first1 == second1) while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) { // जोड़ी मिली if ((first1->data1 * second1->data1) == x1) { found1 = true; cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl; // first को आगे की दिशा में ले जाने के लिए उपयोग किया जाता है first1 = first1->next1; // second को पीछे की दिशा में ले जाने के लिए उपयोग किया जाता है second1 = second1->prev1; } else { if ((first1->data1 * second1->data1) < x1) first1 = first1->next1; else second1 = second1->prev1; } } // अब यदि जोड़ी मौजूद नहीं है if (found1 == false) cout << "कोई जोड़ी नहीं मिली"; } // एक उपयोगिता फ़ंक्शन दिखाता है जो एक नया नोड डालता है // डौबली लिंक्ड लिस्ट की शुरुआत में void insert(struct Node1** head1, int data1){ struct Node1* temp1 = new Node1; temp1->data1 = data1; temp1->next1 = temp1->prev1 = NULL; if (!(*head1)) (*head1) = temp1; else { temp1->next1 = *head1; (*head1)->prev1 = temp1; (*head1) = temp1; } } // ड्राइवर कोड int main(){ // डौबली लिंक्ड लिस्ट बनाएं struct Node1* head1 = NULL; /*insert(&head1, 9); insert(&head1, 8); insert(&head1, 6); insert(&head1, 5); insert(&head1, 4); insert(&head1, 2); insert(&head1, 1); int x1 = 8; */ insert(&head1, 7); insert(&head1, 6); insert(&head1, 5); insert(&head1, 4); insert(&head1, 3); insert(&head1, 2); insert(&head1, 1); int x1 = 6; pairProduct(head1, x1); return 0; }
आउटपुट
(1, 6) (2, 3)
