숫자로 구성된 단일 연결 리스트가 주어졌을 때, 재귀(Recursion)만을 이용해 리스트의 가운데 노드를 찾아보겠습니다. 예를 들어 리스트의 요소가 [12, 14, 18, 36, 96, 25, 62]라면, 정확히 가운데에 위치한 요소는 36입니다.
동작 원리
이 문제는 다음과 같은 절차로 해결할 수 있습니다.
- 재귀 호출을 통해 리스트 끝까지 순회하면서 전체 노드 개수(n)를 셉니다.
- head가 NULL에 도달하면 n을 절반으로 나눕니다.
- 재귀 호출이 되감기면서 각 단계마다 n을 1씩 감소시키고, n이 0이 되는 시점의 노드를 중간 노드로 기록합니다.
즉, 앞으로 진행하며 개수를 세고, 되돌아오며 절반 지점을 찾는 방식입니다.
예제 코드
#include<iostream>
#include<stack>
using namespace std;
class Node {
public:
int data;
Node *next;
};
// 새 노드 생성 및 초기화
Node* getNode(int data) {
Node *newNode = new Node;
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 재귀적으로 노드 수를 세고 중간 노드를 찾는 함수
void midpoint_task(Node* head, int* n, Node** mid) {
if (head == NULL) { // 리스트 끝에 도달
*n /= 2; // 총 개수의 절반 계산
return;
}
*n += 1; // 노드 개수 증가
midpoint_task(head->next, n, mid); // 다음 노드로 재귀 호출
*n -= 1; // 되감기며 카운트 감소
if (*n == 0) { // 절반 지점 도달 시 중간 노드 저장
*mid = head;
}
}
// 중간 노드를 반환하는 래퍼 함수
Node* findMidpoint(Node* head) {
Node* mid = NULL;
int n = 1;
midpoint_task(head, &n, &mid);
return mid;
}
// 리스트 끝에 새 노드 추가
void append(struct Node** start, int key) {
Node* new_node = getNode(key);
Node *p = (*start);
if (p == NULL) {
(*start) = new_node;
return;
}
while (p->next != NULL) {
p = p->next;
}
p->next = new_node;
}
int main() {
Node *start = NULL;
int arr[] = {12, 14, 18, 36, 96, 25, 62};
int size = sizeof(arr)/sizeof(arr[0]);
// 배열의 값을 연결 리스트로 변환
for (int i = 0; i<size; i++) {
append(&start, arr[i]);
}
Node* res = findMidpoint(start);
cout << "Mid point is: " << res->data;
}실행 결과
Mid point is: 36
코드 설명
- getNode(): 데이터 값을 담은 새로운 노드를 생성하고 초기화합니다.
- midpoint_task(): 핵심 재귀 함수입니다. head가 NULL이 될 때까지 앞으로 진행하며 노드 수를 세고, 재귀가 되감길 때 n을 감소시켜 절반 지점의 노드를 포인터로 저장합니다.
- findMidpoint(): 초기값을 설정하고 재귀 함수를 호출한 뒤 중간 노드를 반환하는 래퍼(wrapper) 함수입니다.
- append(): 리스트 마지막에 새 노드를 추가하여 배열 데이터를 연결 리스트로 만듭니다.
복잡도 분석
- 시간 복잡도: O(n) — 리스트를 한 번 순회하므로 노드 수에 비례합니다.
- 공간 복잡도: O(n) — 재귀 호출 스택이 노드 수만큼 쌓입니다.
참고로 반복문과 두 개의 포인터(느린 포인터·빠른 포인터)를 사용하면 공간 복잡도를 O(1)로 줄일 수 있지만, 이번 예제는 재귀적 접근 방식을 학습하기 위한 것입니다.