এই সমস্যাতে, একটি লিংকড লিস্ট দেওয়া আছে যাতে মান, লিংক পয়েন্টার এবং একটি আربیট্রারি পয়েন্টার আছে। আমাদের কাজ হলো আربيট্রারি পয়েন্টারকে লিস্টের পরবর্তী বড় মানযুক্ত নোড নির্দেশ করানো।
উদাহরণ:
এখানে দেখা যাচ্ছে 8 নির্দেশ করছে 12-কে, 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 overloaded \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 overloaded Traversing linked List Using Next Pointer 32, 87, 12, 45, Using Arbit Pointer 12, 32, 45, 87,
