ในปัญหานี้ เราได้รับรายการลิงก์ที่มีค่า ตัวชี้ลิงก์ และตัวชี้ตามอำเภอใจ งานของเราคือทำให้ตัวชี้โดยพลการชี้ไปที่ค่าขนาดใหญ่ถัดไปในรายการ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ในที่นี้ เราจะเห็น 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,