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

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

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

ที่นี่ เราสามารถเห็นได้ว่า 8 ชี้ไป 12, 12 ไป 41, 41 ไป 54, 54 ไป 76 ซึ่งเป็นองค์ประกอบที่มากกว่าต่อเนื่องของ linked list

เพื่อแก้ปัญหานี้ เราจะใช้ merge sort algorithm เพื่อเรียงลำดับองค์ประกอบและใช้รายการที่เรียงลำดับแล้วเป็น linked list สำหรับ arbitrary pointer

สำหรับสิ่งนี้ เราจะใช้ merge sort algorithm บน linked list โดยถือ arbitrary pointer ว่าเป็น primary pointer สำหรับการเรียงลำดับและ linked list นี่จะแก้ปัญหา คือ arbitrary pointer แต่ละตัวจะชี้ไปยังโหนดที่ใหญ่กว่าถัดไป

ตัวอย่าง

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

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next, *arbit;
};

Node* SortedMerge(Node* a, Node* b);
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef);

void MergeSort(Node** headRef) {
    Node* head = *headRef;
    Node* a, *b;
    if ((head == NULL) || (head->arbit == NULL))
        return;
    FrontBackSplit(head, &a, &b);
    MergeSort(&a);
    MergeSort(&b);
    *headRef = SortedMerge(a, b);
}

Node* SortedMerge(Node* a, Node* b) {
    Node* result = NULL;
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);
    if (a->data <= b->data) {
        result = a;
        result->arbit = SortedMerge(a->arbit, b);
    } else {
        result = b;
        result->arbit = SortedMerge(a, b->arbit);
    }
    return (result);
}

void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) {
    Node* fast, *slow;
    if (source == NULL || source->arbit == NULL) {
        *frontRef = source;
        *backRef = NULL;
        return;
    }
    slow = source, fast = source->arbit;
    while (fast != NULL) {
        fast = fast->arbit;
        if (fast != NULL) {
            slow = slow->arbit;
            fast = fast->arbit;
        }
    }
    *frontRef = source;
    *backRef = slow->arbit;
    slow->arbit = NULL;
}

void addNode(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    new_node->arbit = NULL;
    (*head_ref) = new_node;
}

Node* populateArbitraray(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
        temp->arbit = temp->next;
        temp = temp->next;
    }
    MergeSort(&head);
    return head;
}

int main() {
    Node* head = NULL;
    addNode(&head, 45);
    addNode(&head, 12);
    addNode(&head, 87);
    addNode(&head, 32);
    Node *ahead = populateArbitraray(head);
    cout << "\t\tArbitrary pointer overloaded \n Traversing linked List\n";
    cout << "Using Next Pointer\n";
    while (head != NULL) {
        cout << head->data << ", ";
        head = head->next;
    }
    printf("\nUsing Arbit Pointer\n");
    while (ahead != NULL) {
        cout << ahead->data << ", ";
        ahead = ahead->arbit;
    }
    return 0;
}

ผลลัพธ์

Arbitrary pointer overloaded Traversing linked List
Using Next Pointer
32, 87, 12, 45,
Using Arbit Pointer
12, 32, 45, 87,