C++でのリンクリストの代替ソート

リンクリストは、要素を格納し、次のデータノードへのポインタも格納する線形データ構造です。

リンクリストのソートに関するこの問題では、代替ソートとは、1番目のノードに最小値のデータが含まれ、2番目のノードに最大値のデータが含まれ、3番目に次の最小値（2番目の最小値）が含まれるようにソートすることを意味します。等々。この交互の最大値と最小値のパターンは、リンクリストの交互の並べ替えで作成されます。

問題をよりよく理解するために例を見てみましょう-

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.

今、私たちが問題について知っているように。この問題の解決策を見つけようとします。したがって、最小値と最大値を交互に切り替える必要があるため、それに応じてリンクリストを並べ替える必要があります。このために、任意のリンクリストの並べ替えを使用できます。次に、最初から1つの値を取り、最後から1つの値を取ります。重複を避けるために、2つの異なるリストを使用することをお勧めします。 2つの半分の後者を逆にしてから、交互の順序でマージします。マージソート手法のいくつかのセクションを使用する必要があるため、ソートにもマージソートは非常に効率的です。

アルゴリズム

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