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 tiếp theo trong danh sách.
Hãy lấy một ví dụ để hiểu vấn đề,
Ở đây, chúng ta có thể thấy 8 điểm đến 12, 12 đến 41, 41 đến 54, 54 đến 76 là các phần tử lớn hơn liên tiếp của danh sách được liên kết.
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng thuật toán sắp xếp hợp nhất để sắp xếp các phần tử và sử dụng sắp xếp như một danh sách được liên kết cho con trỏ tùy ý.
Đối với điều này, chúng tôi sẽ sử dụng thuật toán sắp xếp hợp nhất trên danh sách được liên kết coi con trỏ tùy ý là con trỏ chính để sắp xếp và danh sách được liên kết, điều này sẽ giải quyết vấn đề tức là mỗi điểm tùy ý sẽ trỏ đến nút lớn hơn tiếp theo sau đó.
Ví dụ
Chương trình thể hiện việc triển khai giải pháp của chúng tôi,
#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 overlaoded \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;
} Đầu ra
Arbitrary pointer overlaoded Traversing linked List Using Next Pointer 32, 87, 12, 45, Using Arbit Pointer 12, 32, 45, 87,