सी ++ में एक मनमाना सूचक के साथ एक लिंक्ड सूची में अगले उच्च मूल्य नोड को इंगित करें

इस समस्या में, हमें एक मूल्य, लिंक सूचक और एक मनमाना सूचक के साथ एक लिंक्ड सूची दी जाती है। हमारा काम सूची में अगले बड़े मूल्य को इंगित करने के लिए मनमाना सूचक बिंदु बनाना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

यहां, हम 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 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,