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