C++のリンクリスト内の最大値の右側のノードへのポイントアービットポインタ

この問題では、値、リンクポインター、および任意のポインターを持つリンクリストが提供されます。私たちのタスクは、リンクリストの右側にある最大値を指すように任意のポインターポイントを作成することです。

問題を理解するために例を見てみましょう

ここでは、リンクリストの次の任意のポインタを見ることができます。これは、リンクリストの右側にある最大の要素を指しています。

12 -> 76, 76 -> 54, 54 -> 8, 8 -> 41

この問題を解決するには、ノードの右側にある最大の要素を見つける必要があります。このために、リンクリストを逆方向にトラバースし、すべての最大の要素を見つけ始めます。次に、各ノードで、維持している最大のノードに任意のポイントを作成します。

例

ソリューションの実装を示すプログラム

#include<bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   Node* next, *arbitrary;
};
Node* reverseList(Node *head){
   Node *prev = NULL, *current = head, *next;
   while (current != NULL){
      next = current->next;
      current->next = prev;
      prev = current;
      current = next;
   }
   return prev;
}
Node* populateArbitraray(Node *head){
   head = reverseList(head);
   Node *max = head;
   Node *temp = head->next;
   while (temp != NULL){
      temp->arbitrary = max;
      if (max->data < temp->data)
         max = temp;
      temp = temp->next;
   }
   return reverseList(head);
}
Node *insertNode(int data) {
   Node *new_node = new Node;
   new_node->data = data;
   new_node->next = NULL;
   return new_node;
}
int main() {
   Node *head = insertNode(12);
   head->next = insertNode(76);
   head->next->next = insertNode(54);
   head->next->next->next = insertNode(8);
   head->next->next->next->next = insertNode(41);
   head = populateArbitraray(head);
   printf("Linked List with Arbitrary Pointer: \n");
   while (head!=NULL){
      cout<<head->data<<"->";
      if (head->next)
         cout<<head->next->data;
      else
         cout<<"NULL";
      cout<<": "<<head->data<<"->";
      if (head->arbitrary)
         cout<<head->arbitrary->data;
      else
         cout<<"NULL";
      cout << endl;
      head = head->next;
   }
   return 0;
}

出力

Linked List with Arbitrary Pointer:
12->76: 12->76
76->54: 76->54
54->8: 54->41
8->41: 8->41
41->NULL: 41->NULL