การเรียงลำดับทางเลือกของรายการที่เชื่อมโยงใน C ++

รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นที่เก็บองค์ประกอบและจัดเก็บตัวชี้ไปยังโหนดข้อมูลถัดไป

ในปัญหานี้เกี่ยวกับการเรียงลำดับของรายการที่เชื่อมโยง การเรียงลำดับทางเลือกหมายถึงการเรียงลำดับในลักษณะที่โหนดที่ 1 มีข้อมูลที่มีค่าต่ำสุด โหนดที่ 2 ประกอบด้วยข้อมูลที่มีมูลค่าสูงสุด อันดับที่ 3 ด้วยค่าต่ำสุดถัดไป (ค่าต่ำสุดที่สอง) และอื่นๆ รูปแบบของ maxima และ minimas สำรองนี้ถูกสร้างขึ้นในการจัดเรียงแบบอื่นของรายการที่เชื่อมโยง

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากันดีกว่า −

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.

ตอนนี้อย่างที่เราทราบเกี่ยวกับปัญหา เราจะพยายามหาทางแก้ไขปัญหานี้ ดังนั้น เนื่องจากเราต้องสลับ minima และ maxima เราจึงควรจัดเรียงรายการที่เชื่อมโยงตามลำดับ สำหรับสิ่งนี้ คุณสามารถใช้การเรียงลำดับรายการที่เชื่อมโยงได้ จากนั้นเราจะเอาค่าหนึ่งค่าจากจุดเริ่มต้นและค่าหนึ่งจากจุดสิ้นสุด ควรใช้สองรายการที่แตกต่างกันเพื่อหลีกเลี่ยงการทับซ้อนกัน เราจะย้อนกลับส่วนหลังของทั้งสองส่วนแล้วรวมกลับในลำดับอื่น เนื่องจากเราต้องใช้เทคนิคการเรียงลำดับการผสานบางส่วน การเรียงลำดับการผสานจึงค่อนข้างมีประสิทธิภาพ

อัลกอริทึม

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