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