이 글에서는 C++를 사용하여 두 개의 정렬된 단일 연결 리스트(singly linked list)를 하나의 정렬된 리스트로 병합하는 방법을 알아봅니다. 정렬된 연결 리스트 병합은 면접에서 자주 등장하는 대표적인 알고리즘 문제이며, 재귀적 접근 방식으로 깔끔하게 해결할 수 있습니다.
문제 정의
두 개의 정렬된 단일 연결 리스트가 주어졌을 때, 이 두 리스트를 하나의 정렬된 연결 리스트로 병합하는 함수를 작성해야 합니다.
리스트1: 10->15->17->20 리스트2: 5->9->13->19 결과: 5->9->10->13->15->17->19->20
알고리즘 설계
병합 과정은 다음과 같은 순서로 진행됩니다.
1. 두 리스트를 동시에 순회합니다.
1.1. list1->data < list2->data인 경우
1.1.1 list1->data를 새 리스트에 추가하고 list1 포인터를 다음 노드로 이동합니다.
1.2. list2->data <= list1->data인 경우
1.2.1 list2->data를 새 리스트에 추가하고 list2 포인터를 다음 노드로 이동합니다.
2. 두 리스트 중 하나라도 끝날 때까지 위 과정을 반복합니다.
3. 남은 노드들을 결과 리스트 뒤에 이어 붙인 후 최종 리스트를 반환합니다.
구현 예제 코드
아래는 재귀 함수를 활용하여 두 정렬 리스트를 병합하는 전체 C++ 프로그램입니다.
#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct node {
int data;
struct node *next;
};
node *createList(int *arr, int n){
node *head, *p;
p = head = new node;
head->data = arr[0];
head->next = NULL;
for (int i = 1; i < n; ++i) {
p->next = new node;
p = p->next;
p->data = arr[i];
p->next = NULL;
}
return head;
}
void displayList(node *head){
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
node *mergeSortedLists(node *head1, node *head2){
node *result = NULL;
if (head1 == NULL) {
return head2;
}
if (head2 == NULL) {
return head1;
}
if (head1->data < head2->data) {
result = head1;
result->next = mergeSortedLists(head1->next, head2);
} else {
result = head2;
result->next = mergeSortedLists(head1, head2->next);
}
return result;
}
int main(){
int arr1[] = {10, 15, 17, 20};
int arr2[] = {5, 9, 13, 19};
node *head1, *head2, *result = NULL;
head1 = createList(arr1, SIZE(arr1));
head2 = createList(arr2, SIZE(arr2));
cout << "첫 번째 정렬 리스트:" << endl;
displayList(head1);
cout << "두 번째 정렬 리스트:" << endl;
displayList(head2);
result = mergeSortedLists(head1, head2);
cout << "병합된 최종 리스트:" << endl;
displayList(result);
return 0;
}
코드 핵심 로직 설명
- createList: 배열 데이터를 받아 연결 리스트 형태로 변환하는 헬퍼 함수입니다. 첫 노드를 생성한 뒤 나머지 요소들을 순서대로 연결합니다.
- displayList: 헤드 포인터부터 시작해 각 노드의 데이터를 출력하며 리스트 끝까지 순회합니다.
- mergeSortedLists: 재귀적으로 두 리스트의 헤드 값을 비교하여 더 작은 쪽을 결과 노드로 선택하고, 해당 리스트의 다음 노드와 나머지 리스트를 인자로 재귀 호출합니다. 한쪽 리스트가 비어 있으면(NULL) 반대편 리스트를 그대로 반환하여 종료 조건을 처리합니다.
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력을 확인할 수 있습니다.
첫 번째 정렬 리스트: 10 15 17 20 두 번째 정렬 리스트: 5 9 13 19 병합된 최종 리스트: 5 9 10 13 15 17 19 20
시간 및 공간 복잡도
- 시간 복잡도: O(n + m) — 두 리스트의 모든 노드를 한 번씩만 방문하므로 리스트 길이의 합에 비례합니다.
- 공간 복잡도: 재귀 방식은 호출 스택 때문에 O(n + m)의 추가 공간이 필요합니다. 스택 오버플로우가 우려되는 경우 더미 노드(dummy node)를 사용한 반복문 방식으로 구현하면 O(1) 공간으로 최적화할 수 있습니다.