अवधारणा
सकारात्मक विशिष्ट तत्वों की दी गई क्रमबद्ध डबल लिंक्ड सूची के संबंध में, हमारा कार्य डबल लिंक्ड सूची में जोड़े निर्धारित करना है जिसका उत्पाद दिए गए मान x के बराबर है, बिना किसी अतिरिक्त स्थान का उपभोग किए।
इनपुट
List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9 x = 8
आउटपुट
(1, 8), (2, 4)
इनपुट
List1 = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 x = 6
आउटपुट
(1, 4), (2,3)
विधि
साधारण दृष्टिकोण . के अनुसार इस समस्या के लिए, हम दो नेस्टेड लूप को लागू करने वाली लिंक की गई सूची को पार करते हैं और सभी जोड़े निर्धारित करते हैं और एक्स के बराबर उत्पाद वाले जोड़े के लिए सत्यापित करते हैं। यहां, इस समस्या के लिए समय जटिलता ओ (एन ^ 2) होगी, जहां एन डबल लिंक्ड सूची में नोड्स की कुल संख्या है।
एक कुशल समाधान इसके लिए इस समस्या पर चर्चा की गई है। यहाँ एल्गोरिथम के चरण दिए गए हैं -
डबल लिंक की गई सूची में उम्मीदवार तत्वों को निर्धारित करने के लिए हम दो पॉइंटर वेरिएबल को इनिशियलाइज़ करते हैं।
हम डबल लिंक्ड लिस्ट की शुरुआत के साथ first1 को इनिशियलाइज़ करते हैं, जिसका मतलब है, first1=head और सेकेंड 1 को डबल लिंक्ड लिस्ट के आखिरी नोड के साथ इनिशियलाइज़ करते हैं, जिसका मतलब है, दूसरा1=last_node।
अब हम पहले और दूसरे पॉइंटर्स को पहले और आखिरी नोड्स के रूप में इनिशियलाइज़ करते हैं। इस मामले में हमारे पास रैंडम एक्सेस नहीं है, इसलिए दूसरा पॉइंटर निर्धारित करने के लिए, हम सेकेंड 1 को इनिशियलाइज़ करने के लिए सूची पर जाते हैं।
यह देखा गया है कि यदि पहले और दूसरे 1 का वर्तमान योग x से छोटा है, तो हम पहले 1 को आगे की दिशा में ले जाते हैं। अन्यथा यदि प्रथम1 और द्वितीय1 का वर्तमान योग x से अधिक है, तो हम सेकंड1 को पीछे की दिशा में ले जाते हैं।
अंत में, लूप समाप्ति की स्थिति भी सरणियों से भिन्न होती है। इस स्थिति में, लूप तब समाप्त होता है जब दो में से कोई भी पॉइंटर NULL हो जाता है, या वे एक-दूसरे को क्रॉस करते हैं (सेकेंड1->नेक्स्ट =फर्स्ट1), या वे एक जैसे हो जाते हैं (first1 ==second1)।
उदाहरण
// C++ program to find a pair with
// given product x in sorted Doubly
// Linked List
#include <bits/stdc++.h>
using namespace std;
//Shows Doubly Linked List Node
struct Node1 {
int data1;
struct Node1 *next1, *prev1;
};
// Shows function to determine pair whose product
// equal to given value x
void pairProduct(struct Node1* head1, int x1){
// Now set two pointers,
// first to the beginning of DLL and second to the end of DLL.
struct Node1* first1 = head1;
struct Node1* second1 = head1;
while (second1->next1 != NULL)
second1 = second1->next1;
// Used to track if we find a pair or not
bool found1 = false;
// Now the loop terminates when either of two pointers
// become NULL, or they cross each other (second1->next1
// == first1), or they become same (first1 == second1)
while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
// pair found
if ((first1->data1 * second1->data1) == x1) {
found1 = true;
cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
// Used to move first in forward direction
first1 = first1->next1;
// Used to move second in backward direction
second1 = second1->prev1;
} else {
if ((first1->data1 * second1->data1) < x1)
first1 = first1->next1;
else
second1 = second1->prev1;
}
}
// Now if pair is not present
if (found1 == false)
cout << "No pair found";
}
// Shows a utility function to insert a new node at the
// beginning of doubly linked list
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;
}
}
// Driver Code
int main(){
// Create Doubly Linked List 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)