연결 리스트란?
연결 리스트(linked list)는 요소들을 순차적으로 저장하면서, 각 노드가 다음 데이터 노드를 가리키는 포인터까지 함께 보관하는 선형 자료구조입니다.
교차 정렬(Alternate Sort)이란?
연결 리스트 정렬 문제에서 교차 정렬은 최솟값과 최댓값을 번갈아 배치하는 정렬 방식을 의미합니다. 즉, 첫 번째 노드에는 가장 작은 값, 두 번째 노드에는 가장 큰 값, 세 번째 노드에는 두 번째로 작은 값, 네 번째 노드에는 두 번째로 큰 값을 배치하는 식으로 진행됩니다.
예시를 통해 문제를 더 쉽게 이해해 보겠습니다.
입력 : 3 > 4 > 21 > 67 > 1 > 8
출력 : 1 > 67 > 3 > 21 > 4 > 8
설명 :
요소를 오름차순으로 정렬하면 1, 3, 4, 8, 21, 67입니다.
원하는 출력을 만들려면 정렬된 목록의 앞에서 하나, 뒤에서 하나를 번갈아 가져와 배치하면 됩니다.
문제 해결 접근 방법
최솟값과 최댓값을 번갈아 배치해야 하므로, 먼저 연결 리스트를 오름차순으로 정렬한 뒤 앞쪽과 뒤쪽에서 하나씩 번갈아 가져오는 전략을 사용합니다.
정렬에는 어떤 연결 리스트 정렬 알고리즘이든 사용할 수 있지만, 이 문제는 병합 과정을 활용해야 하므로 병합 정렬(Merge Sort)이 특히 효율적입니다. 정렬 후에는 리스트를 반으로 나누고, 뒤쪽 절반을 뒤집은 다음, 두 리스트를 교차로 병합하여 결과를 만듭니다.
알고리즘 단계
1단계 : 병합 정렬 기법으로 연결 리스트를 정렬합니다.
2단계 : 원래 연결 리스트 길이의 절반씩 두 개의 연결 리스트를 만들고,
앞쪽 절반은 첫 번째 리스트에, 뒤쪽 절반은 두 번째 리스트에 담습니다.
3단계 : 두 번째 연결 리스트를 뒤집어 새로운 연결 리스트에 저장합니다.
4단계 : 첫 번째 리스트와 뒤집힌 리스트의 요소를 교차로 사용하여 결과 연결 리스트를 생성합니다.
C++ 구현 예제
#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
위 코드는 병합 정렬로 리스트를 오름차순 정렬한 뒤, 빠른/느린 포인터(fast/slow pointer) 기법으로 리스트를 반으로 분할하고, 뒤쪽 절반을 뒤집어 앞쪽 절반과 교차 병합함으로써 최솟값과 최댓값이 번갈아 나오는 교차 정렬 결과를 얻습니다.