C ++中链表的替代排序

链表是一个线性数据结构，该结构存储元素并且还存储指向下一个数据节点的指针。

在对链表进行排序的问题中，备用排序意味着按以下方式进行排序：第一个节点包含最小值的数据，第二个节点包含最大值的数据，第三个节点包含下一个最小值（第二个最小值）等等。交替最大值和最小值的这种模式是在链表的交替排序中创建的。

让我们举个例子来更好地理解问题-

Input : 3 > 4 > 21 >67 > 1 > 8.
Output : 1 > 67 > 3 > 21 > 4 > 8.
Explanation :
元素的排序顺序是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 << "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