एक लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जो एलिमेंट्स को स्टोर करती है और अगले डेटा नोड का पॉइंटर भी स्टोर करती है।
लिंक्ड लिस्ट की क्रमबद्ध करने की इस समस्या में, वैकल्पिक क्रमबद्ध करने का अर्थ है इस तरह क्रमबद्ध करना कि पहला नोड न्यूनतम मान वाला डेटा रखे, दूसरा नोड अधिकतम मान वाला डेटा रखे, तीसरा अगला न्यूनतम (दूसरा न्यूनतम मान) रखे और इसी तरह। वैकल्पिक मैक्सिमा और मिनिमा का यह पैटर्न लिंक्ड लिस्ट की वैकल्पिक क्रमबद्ध करने में बनाया जाता है।
आइए एक उदाहरण लेते हैं समस्या को बेहतर ढंग से समझने के लिए:
इनपुट: 3 > 4 > 21 > 67 > 1 > 8. आउटपुट: 1 > 67 > 3 > 21 > 4 > 8. व्याख्या: एलिमेंट्स का क्रमबद्ध क्रम 1, 3, 4, 8, 21, 67 है। आवश्यक आउटपुट के लिए हमें शुरुआत से एक मान और अंत से एक मान लेना होगा और यह परिणाम देता है।
अब, चूंकि हम समस्या के बारे में जानते हैं। हम इस समस्या का समाधान खोजने की कोशिश करेंगे। तो, अब चूंकि हमें वैकल्पिक मिनिमा और मैक्सिमा की आवश्यकता है, हमें लिंक्ड लिस्ट को तदनुसार क्रमबद्ध करना चाहिए। इसके लिए किसी भी लिंक्ड लिस्ट क्रमबद्ध करने का उपयोग किया जा सकता है। फिर हम शुरुआत से एक मान और अंत से एक मान लेंगे। ओवरलैप से बचने के लिए दो अलग-अलग लिस्ट का उपयोग करना बेहतर है। हम बाद वाली दो आधी लिस्ट को रिवर्स करेंगे और फिर उन्हें वैकल्पिक क्रम में वापस मर्ज करेंगे। चूंकि हमें मर्ज क्रमबद्ध करने की तकनीक के कुछ खंडों का उपयोग करना है, क्रमबद्ध करने के लिए मर्ज क्रमबद्ध करना काफी कुशल है।
एल्गोरिदम
चरण 1: मर्ज क्रमबद्ध तकनीक का उपयोग करके लिंक्ड लिस्ट को क्रमबद्ध करें। चरण 2: मूल लिंक्ड लिस्ट की लंबाई के आधे आकार की दो लिंक्ड लिस्ट बनाएं। अब, आधे को पहली आधी लिंक्ड लिस्ट में और दूसरे आधे को दूसरी आधी लिंक्ड लिस्ट में रखें। चरण 3: दूसरी लिंक्ड लिस्ट को रिवर्स करें और नई लिंक्ड लिस्ट में स्टोर करें (रिवर्सल के लिए आवश्यक)। चरण 4: पहली और रिवर्स लिंक्ड लिस्ट का उपयोग करके परिणाम लिंक्ड लिस्ट बनाएं। दोनों लिस्ट के एलिमेंट्स का वैकल्पिक क्रम में उपयोग करें।
उदाहरण
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; }; Node* getNode(int data){ Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = NULL; return newNode; } void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) ; Node* SortedMerge(Node* a, Node* b) ; void MergeSort(Node** headRef) ; void alternateMerge(Node* head1, Node* head2) ; Node* altSortLinkedList(Node* head) ; void printList(Node* head) ; static void reverse(Node** head_ref){ Node* prev = NULL; Node* current = *head_ref; Node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev; } int main(){ Node* head = getNode(3); head->next = getNode(4); head->next->next = getNode(21); head->next->next->next = getNode(67); head->next->next->next->next = getNode(1); head->next->next->next->next->next = getNode(8); cout << "प्रारंभिक सूची: "; printList(head); head = altSortLinkedList(head); cout << "\nक्रमबद्ध सूची: "; printList(head); return 0; } void FrontBackSplit(Node* source, Node** frontRef, Node** backRef){ Node* fast; Node* slow; if (source == NULL || source->next == NULL) { *frontRef = source; *backRef = NULL; } else { slow = source; fast = source->next; while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } *frontRef = source; *backRef = slow->next; slow->next = NULL; } } 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->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return result; } void MergeSort(Node** headRef){ Node* head = *headRef; Node *a, *b; if ((head == NULL) || (head->next == NULL)) return; FrontBackSplit(head, &a, &b); MergeSort(&a); MergeSort(&b); *headRef = SortedMerge(a, b); } void alternateMerge(Node* head1, Node* head2){ Node *p, *q; while (head1 != NULL && head2 != NULL) { p = head1->next; head1->next = head2; head1 = p; q = head2->next; head2->next = head1; head2 = q; } } Node* altSortLinkedList(Node* head){ MergeSort(&head); Node *front, *back; FrontBackSplit(head, &front, &back); reverse(&back); alternateMerge(front, back); return front; } void printList(Node* head){ while (head != NULL) { cout << head->data << " "; head = head->next; } } आउटपुट
प्रारंभिक सूची: 3 4 21 67 1 8 क्रमबद्ध सूची: 1 67 3 21 4 8
