इस समस्या में, हमें एक डबल लिंक्ड लिस्ट और एक वैल्यू योग दिया जाता है। हमारा काम डबल लिंक की गई सूची में दिए गए योग के साथ जोड़े ढूंढना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
head − 2 <-> 5 <-> 6 <-> 9 <-> 12 x = 11
आउटपुट
(2, 9), (5, 6)
स्पष्टीकरण
For pairs (2, 9), the sum of values is 11 For pairs (5, 6), the sum of values is 11
समाधान दृष्टिकोण
समस्या का एक सरल समाधान पूरी लिंक्ड-लिस्ट को ट्रेस करना और तत्वों को एक-एक करके लेना और शेष लिंक्ड सूची में उस तत्व को ढूंढना है जिसका योग योग है। यह नेस्टेड लूप का उपयोग करके किया जाता है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<iostream>
using namespace std;
struct Node {
int data;
struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
struct Node *first = head;
int pairCount = 0;
while (first != NULL) {
struct Node *second = first -> next;
while(second != NULL){
if ((first->data + second->data) == sum) {
pairCount++;
cout<<"("<<first->data<<",
"<<second->data<<")\n";
}
second = second -> next;
}
first = first -> next;
}
if (!pairCount)
cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
struct Node *temp = new Node;
temp->data = data;
temp->next = temp->prev = NULL;
if (!(*head))
(*head) = temp;
else{
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
int main() {
struct Node *head = NULL;
insert(&head, 12);
insert(&head, 9);
insert(&head, 6);
insert(&head, 5);
insert(&head, 2);
int sum = 11;
cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
findSumPairs(head, sum);
return 0;
} आउटपुट
Pair in the linked list with sum = 11 : (2, 9) (5, 6)
एक और दृष्टिकोण जो अधिक प्रभावी होता है वह इस तथ्य का उपयोग कर रहा है कि लिंक की गई सूची को क्रमबद्ध किया गया है। इसके लिए हम दो पॉइंटर्स का उपयोग करेंगे, एक शुरुआत में लिंक्ड लिस्ट के शीर्ष पर इंगित करता है। और दूसरा छोर शुरू में लिंक्ड सूची के अंतिम नोड की ओर इशारा करता है।
अब, हम योगफल खोजने के लिए फिर जोड़ देंगे और फिर इसकी तुलना
. से करेंगेgiven sum. If sumVal > sum, move end pointer leftwards. If sumVal < sum, move start pointer rightwards. If sumVal == sum, print both values, move start pointer rightwards.
जब पॉइंटर्स एक-दूसरे को पार करते हैं तो लूप से बाहर निकल जाते हैं। साथ ही, हम पाए गए जोड़ियों की संख्या की गणना करेंगे, यदि यह 0 के बराबर है, तो प्रिंट करें "ऐसा कोई जोड़ा नहीं मिला!"
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<iostream>
using namespace std;
struct Node {
int data;
struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
struct Node *start = head;
struct Node *end = head;
while (end->next != NULL)
end = end->next;
int pairCount = 0;
while (start != NULL && end != NULL && start != end &&
end->next != start) {
if ((start->data + end->data) == sum) {
pairCount++;
cout<<"("<<start->data<<", "<<end->data<<")\n";
start = start->next;
end = end->prev;
}
else if ((start->data + end->data) < sum)
start = start->next;
else
end = end->prev;
}
if (!pairCount)
cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
struct Node *temp = new Node;
temp->data = data;
temp->next = temp->prev = NULL;
if (!(*head))
(*head) = temp;
else{
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
int main() {
struct Node *head = NULL;
insert(&head, 12);
insert(&head, 9);
insert(&head, 6);
insert(&head, 5);
insert(&head, 2);
int sum = 11;
cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
findSumPairs(head, sum);
return 0;
} आउटपुट
Pair in the linked list with sum = 11 : (2, 9) (5, 6)