Danh sách được liên kết là một cấu trúc dữ liệu tuyến tính lưu trữ các phần tử và cũng lưu trữ một con trỏ đến nút dữ liệu tiếp theo.
Trong bài toán sắp xếp danh sách liên kết này, sắp xếp thay thế có nghĩa là sắp xếp theo cách sao cho nút thứ nhất chứa dữ liệu với giá trị nhỏ nhất, nút thứ 2 chứa dữ liệu có giá trị lớn nhất, nút thứ 3 chứa dữ liệu có giá trị nhỏ nhất tiếp theo (giá trị nhỏ nhất thứ hai) và như thế. Mẫu cực đại và cực tiểu thay thế này được tạo trong việc sắp xếp thay thế các danh sách được liên kết.
Hãy lấy một ví dụ để hiểu rõ vấn đề hơn -
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.
Bây giờ, như chúng ta biết về vấn đề. Chúng tôi sẽ cố gắng tìm ra giải pháp cho vấn đề này. Vì vậy, bây giờ vì chúng ta cần xen kẽ cực tiểu và cực đại, chúng ta nên sắp xếp các danh sách được liên kết cho phù hợp. Đối với điều này, có thể sử dụng bất kỳ sắp xếp danh sách liên kết nào. Sau đó, chúng tôi sẽ lấy một giá trị từ đầu và một giá trị từ cuối. Tốt hơn là sử dụng hai danh sách khác nhau để tránh chồng chéo. Chúng tôi sẽ đảo ngược phần sau của hai nửa và sau đó hợp nhất chúng lại theo thứ tự thay thế. Vì chúng ta phải sử dụng một số phần của kỹ thuật sắp xếp hợp nhất, để sắp xếp, sắp xếp hợp nhất cũng khá hiệu quả.
Thuật toán
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.
Ví dụ
#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;
}
} Đầu ra
Initial list: 3 4 21 67 1 8 Sorted list: 1 67 3 21 4 8