연결 목록은 요소를 저장하고 다음 데이터 노드에 대한 포인터도 저장하는 선형 데이터 구조입니다.
이 연결 리스트 정렬 문제에서 대체 정렬은 첫 번째 노드에 최소값의 데이터가 포함되고 두 번째 노드에 최대값이 있는 데이터가 포함되고 세 번째 노드에 다음 최소값(두 번째 최소값)이 포함되는 방식으로 정렬하는 것을 의미합니다. 등등. 이 대체 최대 및 최소 패턴은 연결 목록의 대체 정렬에서 생성됩니다.
문제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -
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