문제 소개
단일 연결 리스트(Singly Linked List)와 양의 정수 N이 입력으로 주어진 상황을 가정해 보겠습니다. 목표는 재귀(recursion)를 활용하여 리스트의 뒤에서 N번째에 해당하는 노드를 찾아내는 것입니다. 예를 들어 입력 리스트가 a → b → c → d → e → f 형태이고 N이 4라면, 뒤에서 4번째 노드는 c가 됩니다.
해결 아이디어는 간단합니다. 먼저 재귀 호출을 통해 리스트의 마지막 노드까지 진입한 뒤, 재귀에서 되돌아오는 과정(백트래킹) 동안 카운트 값을 하나씩 증가시킵니다. 그리고 카운트가 N과 같아지는 순간, 현재 노드의 포인터를 결과로 반환하면 됩니다.
입출력 시나리오
입력 − 리스트: 1 → 5 → 7 → 12 → 2 → 96 → 33, N=3
출력 − 뒤에서 N번째 노드는: 2
설명 − 뒤에서 세 번째에 위치한 노드의 값은 2입니다.
입력 − 리스트: 12 → 53 → 8 → 19 → 20 → 96 → 33, N=8
출력 − 해당 노드가 존재하지 않습니다.
설명 − 리스트에 노드가 7개뿐이므로 뒤에서 8번째 노드는 존재할 수 없습니다.
프로그램의 접근 방식
이 접근법에서는 재귀를 이용해 먼저 리스트의 끝까지 도달한 후, 백트래킹하는 동안 static 카운트 변수를 증가시킵니다. 카운트가 입력값 N과 같아지는 즉시 현재 노드의 포인터를 결과 변수에 저장합니다.
int형 데이터 멤버와 다음 노드를 가리키는 Node 포인터를 가지는 구조체 Node를 정의합니다.
함수 addtohead(Node** head, int data)는 노드를 헤드에 추가하여 단일 연결 리스트를 만드는 데 사용됩니다.
위 함수를 이용해 첫 번째 노드를 head 포인터로 하는 단일 연결 리스트를 생성합니다.
함수 display(Node* head)는 헤드 노드부터 시작하여 연결 리스트 전체를 출력합니다.
N을 양의 정수로 입력받습니다.
함수 findNode(Node* head, int n1)는 헤드 포인터와 n1을 받아, 뒤에서 n1번째 노드를 찾으면 결과를 출력합니다.
뒤에서 n1번째 노드를 가리킬 포인터 nlast를 선언합니다.
searchNthLast(head, n1, &nlast)를 호출하여 해당 노드를 탐색합니다.
함수 searchNthLast(Node* head, int n1, Node** nlast)는 head를 첫 노드로 하는 연결 리스트에서 뒤에서 n1번째 노드의 포인터를 반환합니다.
static 카운트 변수를 선언합니다.
head가 NULL이면 아무 작업 없이 반환합니다.
tmp = head->next 로 설정합니다.
searchNthLast(tmp, n1, nlast)를 재귀 호출하여 마지막 노드까지 순회합니다.
재귀에서 돌아온 후 count를 1 증가시킵니다.
count가 n1과 같아지면 *nlast = head 로 설정합니다.
마지막으로 nlast가 가리키는 노드의 값을 출력합니다.
복잡도 분석
시간 복잡도: O(n) — 리스트를 한 번만 순회합니다.
공간 복잡도: O(n) — 재귀 호출 스택이 추가로 사용됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
void addtohead(Node** head, int data){
Node* nodex = new Node;
nodex->data = data;
nodex->next = (*head);
(*head) = nodex;
}
void searchNthLast(Node* head, int n1, Node** nlast){
static int count=0;
if (head==NULL){
return;
}
Node* tmp=head->next;
searchNthLast(tmp, n1, nlast);
count = count + 1;
if (count == n1){
*nlast = head;
}
}
void findNode(Node* head, int n1){
Node* nlast = NULL;
searchNthLast(head, n1, &nlast);
if (nlast == NULL){
cout << "Node does not exists";
}
else{
cout << "Nth Node from the last is: "<< nlast->data;
}
}
void display(Node* head){
Node* curr = head;
if (curr != NULL){
cout<<curr->data<<" ";
display(curr->next);
}
}
int main(){
Node* head = NULL;
addtohead(&head, 20);
addtohead(&head, 12);
addtohead(&head, 15);
addtohead(&head, 8);
addtohead(&head, 10);
addtohead(&head, 4);
addtohead(&head, 5);
int N = 2;
cout<<"Linked list is :"<<endl;
display(head);
cout<<endl;
findNode(head, N);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Linked list is : 5 4 10 8 15 12 20 Nth Node from the last is: 12