Trỏ con trỏ arbitrary đến nút giá trị lớn nhất bên phải trong danh sách liên kết trong C++

Trong bài toán này, chúng ta được cho một danh sách liên kết có giá trị, con trỏ liên kết (link pointer) và một con trỏ tùy ý (arbitrary pointer). Nhiệm vụ là làm cho con trỏ tùy ý trỏ đến nút có giá trị lớn nhất nằm ở bên phải của nó trong danh sách liên kết.

Ví dụ minh họa:

Ở đây, ta thấy các con trỏ tùy ý của danh sách liên kết, trỏ đến các phần tử lớn nhất bên phải:

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

Để giải bài toán, cần tìm phần tử lớn nhất bên phải của một nút. Ta sẽ duyệt danh sách liên kết theo hướng ngược và bắt đầu tìm tất cả các phần tử lớn nhất, sau đó tại mỗi nút làm cho con trỏ tùy ý trỏ đến nút lớn nhất đang duy trì.

Chương trình minh họa

#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("Danh sách liên kết với con trỏ Arbitrary:\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; 
}

Kết quả

Danh sách liên kết với con trỏ Arbitrary: 
12->76: 12->76 
76->54: 76->54 
54->8: 54->41 
8->41: 8->41 
41->NULL: 41->NULL