सी++ में लिंक्ड सूची की वैकल्पिक छँटाई

लिंक की गई सूची एक रेखीय डेटा संरचना है जो तत्वों को संग्रहीत करती है और अगले डेटा नोड के लिए एक पॉइंटर भी संग्रहीत करती है।

इस समस्या में एक लिंक्ड सूची की छँटाई पर, वैकल्पिक प्रकार का अर्थ है इस तरह से छँटाई करना कि पहले नोड में न्यूनतम मान वाला डेटा हो, दूसरे नोड में अधिकतम मान वाला डेटा हो, तीसरे में अगले न्यूनतम (दूसरा न्यूनतम मान) के साथ डेटा हो। और इसी तरह। वैकल्पिक मैक्सिमा और मिनिमास का यह पैटर्न लिंक्ड सूचियों की वैकल्पिक छँटाई में बनाया गया है।

आइए समस्या को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -

Input : 3 > 4 > 21 >67 > 1 > 8.
Output : 1 > 67 > 3 > 21 > 4 > 8.
Explanation :
Sort order of elements is 1 , 3 , 4 ,8 ,21 ,67. For required output we need to take one value from the beginning and one from end and it outputs the result.

अब, जैसा कि हम समस्या के बारे में जानते हैं। हम इस समस्या का समाधान निकालने का प्रयास करेंगे। इसलिए, अब चूंकि हमें मिनिमा और मैक्सिमा को वैकल्पिक करने की आवश्यकता है, इसलिए हमें लिंक की गई सूचियों को तदनुसार क्रमबद्ध करना चाहिए। इसके लिए किसी भी लिंक्ड लिस्ट सॉर्टिंग का इस्तेमाल किया जा सकता है। फिर हम शुरू से एक मान और अंत से एक मान लेंगे। ओवरलैपिंग से बचने के लिए दो अलग-अलग सूचियों का उपयोग करना बेहतर है। हम दो हिस्सों के उत्तरार्द्ध को उलट देंगे और फिर उन्हें वैकल्पिक क्रम में वापस मर्ज कर देंगे। चूंकि हमें मर्ज सॉर्टिंग तकनीक के कुछ सेक्शन का उपयोग करना होता है, इसलिए सॉर्टिंग के लिए मर्ज सॉर्ट भी काफी कुशल होता है।

एल्गोरिदम

Step 1 : Sort the linked list using merge sort technique.
Step 2 : Create two linked list of half the length of the original linked list. Now, place one half in 
         first half linked list and other half in second half linked list.
Step 3 : reverse the second linked list and store in new linked list (required for reversal ).
Step 4 : Create the result linked list using the first and reverse linked list. Using the elements of both list in alternate order.

उदाहरण

#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 << "Initial list: ";
   printList(head);
   head = altSortLinkedList(head);
   cout << "\nSorted list: ";
   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;
   }
}

आउटपुट

Initial list: 3 4 21 67 1 8
Sorted list: 1 67 3 21 4 8