연결 리스트(Linked List)에 있는 노드들을 두 개씩 짝지어 서로 교환한 뒤 결과를 출력하는 문제를 해결해 보겠습니다. 먼저 예시를 통해 문제를 살펴보겠습니다.
입력 : 1->2->3->4->5->6->NULL
출력 : 2->1->4->3->6->5->NULL
입력 : 1->2->3->4->5->NULL
출력 : 2->1->4->3->5->NULL
입력 : 1->NULL
출력 : 1->NULL
위 예시에서 볼 수 있듯이 인접한 두 노드의 데이터가 서로 맞바뀌고, 노드의 개수가 홀수일 경우 마지막 노드는 그대로 유지됩니다. 이 문제는 두 가지 접근 방식으로 해결할 수 있으며, 두 방식 모두 시간 복잡도는 O(N)입니다(N은 연결 리스트의 크기). 지금부터 두 가지 방법을 하나씩 살펴보겠습니다.
반복문을 이용한 접근 방식
이 방식에서는 연결 리스트의 요소를 처음부터 끝까지 순회하면서, NULL에 도달할 때까지 인접한 두 노드의 데이터를 쌍별로 교환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Node { // 리스트의 노드 구조체
public:
int data;
Node* next;
};
void swapPairwise(Node* head){
Node* temp = head;
// 쌍별 교환을 위해서는 노드가 2개 이상 필요하므로 조건을 검사합니다.
while (temp != NULL && temp->next != NULL) {
swap(temp->data,
temp->next->data); // 데이터 교환
temp = temp->next->next; // 다음 쌍으로 이동
}
}
void push(Node** head_ref, int new_data){ // 리스트에 데이터를 삽입하는 함수
Node* new_node = new Node(); // 새 노드 생성
new_node->data = new_data;
new_node->next = (*head_ref); // 기존 head를 새 노드 뒤에 연결
(*head_ref) = new_node; // 새 노드가 head가 됨
}
void printList(Node* node){ // 연결 리스트를 출력하는 유틸리티 함수
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main(){
Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << "교환 전 연결 리스트\n";
printList(head);
swapPairwise(head);
cout << "\n교환 후 연결 리스트\n";
printList(head);
return 0;
}
실행 결과
교환 전 연결 리스트
1 2 3 4 5
교환 후 연결 리스트
2 1 4 3 5
다음 접근 방식에서도 동일한 로직을 사용하지만, 반복문 대신 재귀 호출을 활용하여 구현합니다.
재귀를 이용한 접근 방식
이 방식에서는 앞서 살펴본 것과 같은 로직을 재귀 함수로 구현합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Node { // 리스트의 노드 구조체
public:
int data;
Node* next;
};
void swapPairwise(struct Node* head){
// 반복문 방식과 동일한 조건 검사
if (head != NULL && head->next != NULL) {
swap(head->data, head->next->data); // 데이터 교환
swapPairwise(head->next->next); // 다음 쌍으로 재귀 호출
}
return; // 조건을 만족하지 않으면 종료
}
void push(Node** head_ref, int new_data){ // 리스트에 데이터를 삽입하는 함수
Node* new_node = new Node(); // 새 노드 생성
new_node->data = new_data;
new_node->next = (*head_ref); // 기존 head를 새 노드 뒤에 연결
(*head_ref) = new_node; // 새 노드가 head가 됨
}
void printList(Node* node){ // 연결 리스트를 출력하는 유틸리티 함수
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main(){
Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << "교환 전 연결 리스트\n";
printList(head);
swapPairwise(head);
cout << "\n교환 후 연결 리스트\n";
printList(head);
return 0;
}
실행 결과
교환 전 연결 리스트
1 2 3 4 5
교환 후 연결 리스트
2 1 4 3 5
코드 동작 원리
두 방식 모두 연결 리스트를 한 쌍씩 순회한다는 공통된 원리로 동작합니다. 각 쌍에 도달하면 두 노드의 데이터를 서로 교환하고, 그다음 쌍으로 이동하여 같은 작업을 반복합니다. 반복문 방식은 while 루프를 통해 순차적으로 진행되는 반면, 재귀 방식은 함수가 스스로를 호출하며 다음 쌍을 처리한다는 차이점이 있습니다.
마무리
이번 튜토리얼에서는 재귀와 반복문 두 가지 방법을 사용하여 주어진 연결 리스트의 요소를 쌍별로 교환하는 문제를 해결해 보았습니다. 또한 C++ 프로그램 구현과 함께 문제 해결 과정 전반을 학습했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.