ชี้ Arbitrary Pointer ไปยังโหนดด้านขวาที่มีค่ามากที่สุดใน Linked List ใน C++

ในปัญหานี้ เราได้รับ linked list ที่มีค่า link pointer และ arbitrary pointer งานของเราคือทำให้ arbitrary pointer ชี้ไปยังค่าที่มากที่สุดซึ่งอยู่ทางขวาของมันใน linked list

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

ที่นี่ เราสามารถเห็น arbitrary pointers ต่อไปนี้ของ linked list ซึ่งชี้ไปยังองค์ประกอบที่มากที่สุดทางขวาของ linked list

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

เพื่อแก้ปัญหานี้ เราต้องหาองค์ประกอบที่มากที่สุดทางขวาของโหนด สำหรับสิ่งนี้ เราจะทำการท่อง linked list ในทิศทางย้อนกลับ และเริ่มหาองค์ประกอบที่มากที่สุดทั้งหมด และที่แต่ละโหนด เราจะทำให้ arbitrary pointer ชี้ไปยังโหนดที่ใหญ่ที่สุดที่เรากำลังรักษาไว้

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#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