C++에서 임의의 포인터를 사용하여 연결 목록에서 다음으로 높은 값 노드를 가리킵니다.

이 문제에서는 값, 링크 포인터 및 임의의 포인터가 있는 연결 목록이 제공됩니다. 우리의 임무는 임의의 포인터가 목록에서 다음 큰 값을 가리키도록 하는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

여기에서 우리는 연결 리스트의 연속적인 더 큰 요소인 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,