Trỏ con trỏ arbitrary đến nút giá trị lớn hơn tiếp theo trong danh sách liên kết 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 và 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 hơn tiếp theo trong danh sách.

Ví dụ minh họa:

Ở đây, ta thấy 8 trỏ đến 12, 12 đến 41, 41 đến 54, 54 đến 76 - các phần tử lớn hơn liên tiếp của danh sách liên kết.

Để giải bài toán, ta sẽ dùng thuật toán sắp xếp trộn (merge sort) để sắp xếp các phần tử và dùng danh sách đã sắp xếp làm danh sách liên kết cho con trỏ tùy ý.

Ta dùng merge sort trên danh sách liên kết, coi con trỏ tùy ý như con trỏ chính để sắp xếp. Điều này giải quyết bài toán: mỗi con trỏ tùy ý sẽ trỏ đến nút lớn hơn tiếp theo.

Chương trình minh họa

#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\tCon trỏ Arbitrary overloaded\n Duyệt danh sách liên kết\n"; 
    cout << "Sử dụng con trỏ Next\n"; 
    while (head != NULL) { 
        cout << head->data << ", "; 
        head = head->next; 
    } 
    printf("\nSử dụng con trỏ Arbit\n"); 
    while (ahead != NULL) { 
        cout << ahead->data << ", "; 
        ahead = ahead->arbit; 
    } 
    return 0; 
}

Kết quả

Con trỏ Arbitrary overloaded Duyệt danh sách liên kết 
Sử dụng con trỏ Next: 32, 87, 12, 45, 
Sử dụng con trỏ Arbit: 12, 32, 45, 87,