ในปัญหานี้ เราได้รับรายการลิงก์ที่มีค่า ตัวชี้ลิงก์ และตัวชี้ที่กำหนดเอง งานของเราคือทำให้ตัวชี้ที่กำหนดเองชี้ไปที่ค่าที่มากที่สุดซึ่งอยู่ทางด้านขวาของตัวชี้ในรายการที่เชื่อมโยง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ในที่นี้ เราจะเห็นตัวชี้ตามอำเภอใจของรายการที่เชื่อมโยง ซึ่งชี้ไปยังองค์ประกอบที่ยิ่งใหญ่ที่สุดทางด้านขวาของรายการที่เชื่อมโยง
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
