ในปัญหานี้ เราได้รับรายการลิงก์ที่มีค่า ตัวชี้ลิงก์ และตัวชี้ตามอำเภอใจ งานของเราคือทำให้ตัวชี้โดยพลการชี้ไปที่ค่าขนาดใหญ่ถัดไปในรายการ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ในที่นี้ เราจะเห็น 8 จุดถึง 12, 12 ถึง 41, 41 ถึง 54, 54 ถึง 76 ซึ่งเป็นองค์ประกอบที่ใหญ่ขึ้นตามลำดับของรายการที่เชื่อมโยง
เพื่อแก้ปัญหานี้ เราจะใช้อัลกอริธึมการเรียงลำดับการผสานเพื่อจัดเรียงองค์ประกอบและใช้การเรียงลำดับเป็นรายการที่เชื่อมโยงสำหรับตัวชี้ที่กำหนดเอง
สำหรับสิ่งนี้ เราจะใช้อัลกอริธึมการจัดเรียงแบบผสานในรายการที่เชื่อมโยงซึ่งถือว่าตัวชี้ที่กำหนดเองเป็นตัวชี้หลักสำหรับการเรียงลำดับและรายการที่เชื่อมโยง วิธีนี้จะช่วยแก้ปัญหา กล่าวคือ แต่ละจุดโดยพลการจะชี้ไปยังโหนดที่ใหญ่กว่าถัดไป จากนั้นจุดนั้น
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#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;
} ผลลัพธ์
Arbitrary pointer overlaoded Traversing linked List Using Next Pointer 32, 87, 12, 45, Using Arbit Pointer 12, 32, 45, 87,
