ধারণা
ইতিবাচক স্বতন্ত্র উপাদানগুলির একটি প্রদত্ত বাছাই করা দ্বিগুণ লিঙ্কযুক্ত তালিকার ক্ষেত্রে, আমাদের কাজ হল দ্বিগুণ লিঙ্কযুক্ত তালিকায় জোড়া নির্ধারণ করা যার পণ্যটি প্রদত্ত মানের 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)
পদ্ধতি
একটি সরল পদ্ধতি অনুযায়ী এই সমস্যার জন্য, আমরা দুটি নেস্টেড লুপ প্রয়োগ করে লিঙ্কযুক্ত তালিকাটি অতিক্রম করি এবং সমস্ত জোড়া নির্ধারণ করি এবং x এর সমান পণ্য সহ জোড়াগুলির জন্য যাচাই করি। এখানে, এই সমস্যার জন্য সময়ের জটিলতা হবে O(n^2), যেখানে n হল দ্বিগুণ লিঙ্কযুক্ত তালিকায় মোট নোডের সংখ্যা।
একটি দক্ষ সমাধান এই সমস্যার জন্য আলোচনা করা হয়. এখানে অ্যালগরিদমের ধাপ −
বাছাই করা দ্বিগুণ লিঙ্কযুক্ত তালিকায় প্রার্থী উপাদানগুলি নির্ধারণ করতে আমরা দুটি পয়েন্টার ভেরিয়েবল শুরু করি৷
আমরা দ্বৈত লিঙ্কযুক্ত তালিকার শুরু দিয়ে first1 শুরু করি যার অর্থ, first1=head এবং দ্বিগুণ লিঙ্কযুক্ত তালিকার শেষ নোডের সাথে দ্বিতীয়1কে আরম্ভ করি যার অর্থ, দ্বিতীয়1=লাস্ট_নোড।
এখন আমরা প্রথম এবং শেষ নোড হিসাবে প্রথম এবং দ্বিতীয় পয়েন্টার শুরু করি। এই ক্ষেত্রে আমাদের এলোমেলো অ্যাক্সেস নেই, তাই দ্বিতীয় পয়েন্টার নির্ধারণ করতে, দ্বিতীয় 1 আরম্ভ করার জন্য আমরা তালিকাটি পরিদর্শন করি।
এটা দেখা গেছে যে first1 এবং second1 এর বর্তমান যোগফল যদি x থেকে ছোট হয়, তাহলে আমরা first1কে সামনের দিকে নিয়ে যাই। অন্যথায় যদি প্রথম 1 এবং দ্বিতীয় 1 এর বর্তমান যোগফল x থেকে বড় হয়, তাহলে আমরা দ্বিতীয় সেকেন্ড1কে পিছনের দিকে নিয়ে যাই।
অবশেষে, লুপ সমাপ্তির শর্তগুলিও অ্যারে থেকে আলাদা। এই ক্ষেত্রে, লুপ শেষ হয় যখন দুটি পয়েন্টারের মধ্যে একটি NULL হয়ে যায়, অথবা তারা একে অপরকে অতিক্রম করে (দ্বিতীয়1->পরবর্তী =প্রথম1), অথবা তারা একই (প্রথম1 ==দ্বিতীয় 1) হয়ে যায়।
উদাহরণ
// 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)
