Trong bài toán này, chúng ta được cung cấp một danh sách liên kết với một giá trị, con trỏ liên kết và một con trỏ tùy ý. Nhiệm vụ của chúng ta là làm cho con trỏ tùy ý trỏ đến giá trị lớn nhất nằm ở phía bên phải của nó trong danh sách được liên kết.
Hãy lấy một ví dụ để hiểu vấn đề,
Tại đây, chúng ta có thể thấy các con trỏ tùy ý sau đây của danh sách được liên kết, con trỏ này trỏ đến các phần tử lớn nhất ở phía bên phải của danh sách được liên kết.
12 -> 76, 76 -> 54, 54 -> 8, 8 -> 41
Để giải quyết vấn đề này, chúng ta cần tìm phần tử lớn nhất ở bên phải của một nút. Đối với điều này, chúng tôi sẽ duyệt qua danh sách được liên kết theo hướng ngược lại và bắt đầu tìm tất cả các phần tử lớn nhất và sau đó tại mỗi nút sẽ tạo điểm tùy ý đến nút lớn nhất mà chúng tôi đang duy trì.
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#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;
} Đầu ra
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