इस समस्या में, हमें एक डबल लिंक्ड लिस्ट और एक मान sum दिया जाता है। हमारा कार्य डबल लिंक्ड लिस्ट में दिए गए योग वाले जोड़े ढूंढना है।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
head – 2 <-> 5 <-> 6 <-> 9 <-> 12 x = 11
आउटपुट
(2, 9), (5, 6)
व्याख्या
जोड़े (2, 9) के लिए, मानों का योग 11 है। जोड़े (5, 6) के लिए, मानों का योग 11 है।
समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान पूरी लिंक्ड लिस्ट को पार करना और एक-एक करके तत्वों को लेना और शेष लिंक्ड लिस्ट में उस तत्व को ढूंढना है जिसका योग sum के बराबर हो। यह नेस्टेड लूप का उपयोग करके किया जाता है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#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)
एक अन्य दृष्टिकोण जो अधिक प्रभावी होता है, वह इस तथ्य का उपयोग करता है कि लिंक्ड लिस्ट सॉर्टेड है। इसके लिए हम दो पॉइंटर्स का उपयोग करेंगे, एक start शुरू में लिंक्ड लिस्ट के हेड पर इशारा करता है। और दूसरा end शुरू में लिंक्ड लिस्ट के अंतिम नोड पर इशारा करता है।
अब, हम उन्हें जोड़कर sumVal ढूंढेंगे और फिर इसकी तुलना दिए गए sum से करेंगे।
यदि sumVal > sum, तो end पॉइंटर को बाएं ले जाएं। यदि sumVal < sum, तो start पॉइंटर को दाएं ले जाएं। यदि sumVal == sum, तो दोनों मान प्रिंट करें, start पॉइंटर को दाएं ले जाएं।
जब पॉइंटर्स एक-दूसरे को पार कर जाएं तो लूप से बाहर निकल जाएं। साथ ही, हम पाए गए जोड़ों की संख्या गिनेंगे, यदि यह 0 के बराबर है, तो "No Such Pairs found !" प्रिंट करें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#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)
