단일 연결 리스트란?
단일 연결 리스트(singly linked list)는 각 노드가 데이터와 다음 노드를 가리키는 포인터 두 부분으로 구성된 선형 자료구조입니다.
홀수·짝수 교차 연결 리스트(alternate odd and even singly linked list)는 짝수 데이터를 가진 노드와 홀수 데이터를 가진 노드가 번갈아 배치되어 있는 연결 리스트를 의미합니다.
이 문제에서는 주어진 단일 연결 리스트의 원소들을 재배치하여 이러한 형태를 만들어야 하며, 재배치 방식에는 두 가지가 있습니다.
- 첫 번째 원소가 짝수인 경우: 두 번째 원소는 홀수, 세 번째 원소는 다시 짝수가 되어야 합니다.
- 첫 번째 원소가 홀수인 경우: 두 번째 원소는 짝수, 세 번째 원소는 다시 홀수가 되어야 합니다.
문제 예시
개념을 더 잘 이해하기 위해 예제를 살펴보겠습니다. 다음과 같은 연결 리스트가 있다고 가정합니다.
45 > 21 > 2 > 213 > 3 > 34 > 78 > 12
재배치 결과는 아래와 같습니다.
45 > 2 > 21 > 34 > 213 > 78 > 3 > 12
이 리스트에는 짝수 원소(2, 34, 78, 12)와 홀수 원소(45, 21, 213, 3)가 섞여 있습니다. 따라서 짝수 원소들은 짝수 위치에 차례대로 배치하고, 홀수 원소들은 홀수 위치에 차례대로 배치하면 됩니다.
풀이 접근법: 스택 활용
이런 유형의 문제는 여러 방법으로 풀 수 있지만, 가장 간단한 방법 중 하나는 스택을 사용하는 것입니다.
- 짝수 값과 홀수 값을 담기 위한 스택 두 개를 준비합니다.
- 연결 리스트를 순회하면서 순서가 어긋난 노드를 만나면, 예를 들어 짝수 위치에 있는 홀수 노드라면 홀수 스택에, 홀수 위치에 있는 짝수 노드라면 짝수 스택에 해당 노드의 주소를 push합니다.
- 순회가 끝나면 두 스택이 모두 빌 때까지 각 스택의 top에 있는 노드들의 데이터를 서로 교환(swap)합니다.
이 로직을 바탕으로 만든 알고리즘은 다음과 같습니다.
알고리즘
1단계 : 연결 리스트에서 순서가 어긋난 짝수 노드와 홀수 노드를 저장할 스택을 생성한다.
2단계 : 연결 리스트를 순회하며 다음을 수행한다.
2.1 : 순서가 어긋난 홀수 노드(짝수 위치에 있는 경우)는 홀수 스택에 push한다.
2.2 : 순서가 어긋난 짝수 노드(홀수 위치에 있는 경우)는 짝수 스택에 push한다.
3단계 : 두 스택이 모두 빌 때까지 각 스택의 top끼리 데이터를 교환한다. 스택이 비면 연결 리스트가 원하는 형태로 완성된다.
4단계 : 연결 리스트의 원소들을 출력한다.
C++ 예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void printList(struct Node* node);
Node* newNode(int key) {
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
Node* insertBeg(Node* head, int val) {
Node* temp = newNode(val);
temp->next = head;
head = temp;
return head;
}
void OddEvenList(Node* head);
int main() {
Node* head = newNode(45);
head = insertBeg(head, 21);
head = insertBeg(head, 2);
head = insertBeg(head, 213);
head = insertBeg(head, 3);
head = insertBeg(head, 34);
head = insertBeg(head, 78);
head = insertBeg(head, 12);
cout << "Linked List:" << endl;
printList(head);
OddEvenList(head);
cout << "Linked List after "
<< "Rearranging:" << endl;
printList(head);
return 0;
}
void printList(struct Node* node) {
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
void OddEvenList(Node* head) {
stack<Node*> odd;
stack<Node*> even;
int i = 1;
while (head != nullptr) {
if (head->data % 2 != 0 && i % 2 == 0) {
odd.push(head);
}
else if (head->data % 2 == 0 && i % 2 != 0) {
even.push(head);
}
head = head->next;
i++;
}
while (!odd.empty() && !even.empty()) {
swap(odd.top()->data, even.top()->data);
odd.pop();
even.pop();
}
}
실행 결과
Linked List:
12 78 34 3 213 2 21 45
Linked List after Rearranging:
3 78 45 12 213 2 21 34
출력을 확인해 보면 첫 번째 원소가 홀수(3)이므로 두 번째 원소는 짝수(78), 세 번째 원소는 다시 홀수(45)가 되는 식으로 홀수와 짝수가 번갈아 배치된 것을 알 수 있습니다.
복잡도 분석
- 시간 복잡도: O(N) — 연결 리스트를 한 번만 순회하면 됩니다.
- 공간 복잡도: O(N) — 최악의 경우 모든 노드가 스택에 저장될 수 있습니다.
마무리
이처럼 스택 두 개만 활용하면 단일 연결 리스트의 노드를 손쉽게 홀수·짝수가 번갈아 나오도록 재배치할 수 있습니다. 핵심은 잘못된 위치에 있는 노드를 임시로 스택에 보관했다가, 마지막에 서로 짝지어 데이터를 교환하는 것입니다.