数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++中链表的交替排序
链表是一种线性数据结构，它存储元素，并存储指向下一个数据节点的指针。
在这个链表排序问题中，交替排序是指以这样一种方式排序：第一个节点包含最小值数据，第二个节点包含最大值数据，第三个节点包含次最小值数据，以此类推。这种交替最大值和最小值的模式是在链表的交替排序中创建的。
让我们举个例子来更好地理解这个问题：
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
更新于：2019年10月16日
206 次浏览
广告