এই সমস্যায়, আমাদের একটি মান, লিঙ্ক পয়েন্টার এবং একটি নির্বিচারে পয়েন্টার সহ একটি লিঙ্কযুক্ত তালিকা দেওয়া হয়েছে। আমাদের কাজ হল তালিকার পরবর্তী বড় মান নির্দেশ করার জন্য নির্বিচারে পয়েন্টার পয়েন্ট করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
এখানে, আমরা 12 থেকে 8 পয়েন্ট, 12 থেকে 41, 41 থেকে 54, 54 থেকে 76 দেখতে পাচ্ছি যা লিঙ্ক করা তালিকার পরপর বড় উপাদান।
এই সমস্যাটি সমাধান করতে, আমরা উপাদানগুলিকে সাজানোর জন্য মার্জ সর্ট অ্যালগরিদম ব্যবহার করব এবং নির্বিচারে পয়েন্টারের জন্য লিঙ্কযুক্ত তালিকা হিসাবে সাজানোর ব্যবহার করব৷
এর জন্য আমরা সংযুক্ত তালিকায় মার্জ সর্ট অ্যালগরিদম ব্যবহার করব যাতে বাছাই এবং লিঙ্কযুক্ত তালিকার জন্য স্বেচ্ছাচারী পয়েন্টারকে প্রাথমিক পয়েন্টার হিসাবে বিবেচনা করা হয়, এটি সমস্যার সমাধান করবে অর্থাৎ প্রতিটি অবাধ বিন্দু পরবর্তী বড় নোডের দিকে নির্দেশ করবে।
উদাহরণ
আমাদের সমাধানের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next, *arbit;
};
Node* SortedMerge(Node* a, Node* b);
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef);
void MergeSort(Node** headRef) {
Node* head = *headRef;
Node* a, *b;
if ((head == NULL) || (head->arbit == NULL))
return;
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
Node* SortedMerge(Node* a, Node* b) {
Node* result = NULL;
if (a == NULL)
return (b);
else if (b == NULL)
return (a);
if (a->data <= b->data){
result = a;
result->arbit = SortedMerge(a->arbit, b);
} else {
result = b;
result->arbit = SortedMerge(a, b->arbit);
}
return (result);
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) {
Node* fast, *slow;
if (source == NULL || source->arbit == NULL){
*frontRef = source;
*backRef = NULL;
return;
}
slow = source, fast = source->arbit;
while (fast != NULL){
fast = fast->arbit;
if (fast != NULL){
slow = slow->arbit;
fast = fast->arbit;
}
}
*frontRef = source;
*backRef = slow->arbit;
slow->arbit = NULL;
}
void addNode(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
new_node->arbit = NULL;
(*head_ref) = new_node;
}
Node* populateArbitraray(Node *head) {
Node *temp = head;
while (temp != NULL){
temp->arbit = temp->next;
temp = temp->next;
}
MergeSort(&head);
return head;
}
int main() {
Node* head = NULL;
addNode(&head, 45);
addNode(&head, 12);
addNode(&head, 87);
addNode(&head, 32);
Node *ahead = populateArbitraray(head);
cout << "\t\tArbitrary pointer overlaoded \n Traversing linked List\n";
cout<<"Using Next Pointer\n";
while (head!=NULL){
cout << head->data << ", ";
head = head->next;
}
printf("\nUsing Arbit Pointer\n");
while (ahead!=NULL){
cout<<ahead->data<<", ";
ahead = ahead->arbit;
}
return 0;
} আউটপুট
Arbitrary pointer overlaoded Traversing linked List Using Next Pointer 32, 87, 12, 45, Using Arbit Pointer 12, 32, 45, 87,
