এই সমস্যায়, আমাদের একটি দ্বিগুণ লিঙ্কযুক্ত তালিকা এবং একটি মান সমষ্টি দেওয়া হয়েছে৷ আমাদের কাজ হল প্রদত্ত যোগফলের সাথে দ্বিগুণ লিঙ্কযুক্ত তালিকায় জোড়া খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
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)
আরেকটি পদ্ধতি যা আরও কার্যকর হতে পারে তা হল লিঙ্ক করা তালিকাটি সাজানো হয়েছে। এর জন্য আমরা দুটি পয়েন্টার ব্যবহার করব, একটি শুরুতে লিঙ্ক করা তালিকার মাথার দিকে নির্দেশ করে। এবং অন্য প্রান্তটি প্রাথমিকভাবে লিঙ্ক করা তালিকার শেষ নোডের দিকে নির্দেশ করে।
এখন, আমরা sumVal খুঁজে বের করার জন্য তারপর যোগ করব এবং তারপর
এর সাথে তুলনা করব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)
