C ++의 연결 목록에서 끝에서 n 번째 노드를 찾는 재귀 접근 방식

단일 연결 목록과 양의 정수 N이 입력으로 주어집니다. 목표는 재귀를 사용하여 주어진 목록의 끝에서 N 번째 노드를 찾는 것입니다. 입력 목록에 노드 a → b → c → d → e → f가 있고 N이 4이면 끝에서 4번째 노드는 c가 됩니다.

우리는 먼저 목록의 마지막 노드까지 순회하고 재귀(역추적) 증분 수에서 돌아오는 동안 순회합니다. count가 N과 같으면 현재 노드에 대한 포인터를 결과로 반환합니다.

여기에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다 -

입력 − 목록 :- 1 → 5 → 7 → 12 → 2 → 96 → 33 N=3

출력 − 마지막에서 N번째 노드:2

설명 − 마지막 세 번째 노드는 2입니다.

입력 − 목록 :- 12 → 53 → 8 → 19 → 20 →96 → 33 N=8

출력 − 노드가 존재하지 않습니다.

설명 − 목록에는 7개의 노드만 있으므로 마지막 8번째 노드는 불가능합니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

이 접근 방식에서는 먼저 재귀를 사용하여 목록의 끝에 도달하고 역추적하는 동안 정적 카운트 변수를 증가시킵니다. count가 입력 N과 같아지는 즉시 현재 노드 포인터를 반환합니다.

• int 데이터 부분이 있는 Node 구조와 다음 포인터로 Node를 사용합니다.

• addtohead(Node** head, int data) 함수는 단일 연결 리스트를 생성하기 위해 헤드에 노드를 추가하는 데 사용됩니다.

• 첫 번째 노드에 대한 포인터로 head를 사용하여 위의 함수를 사용하여 단일 연결 목록을 만듭니다.

• 기능 display(Node* head)는 헤드 노드부터 연결 리스트를 출력하는데 사용됩니다.

• N을 양의 정수로 취하십시오.

• findNode(Node* head, int n1) 함수는 head와 n1에 대한 포인터를 받아 끝에서 n1번째 노드를 찾았을 때 결과를 출력합니다.

• 끝에서 n1번째 노드를 가리키는 포인터로 폭발합니다.

• searchNthLast(head, n1, &nlast)를 호출하여 해당 노드를 찾습니다.

• searchNthLast(Node* head, int n1, Node** nlast) 함수는 head를 첫 번째 노드로 사용하여 연결 목록의 끝에서 n1번째 마지막 노드에 대한 포인터를 반환합니다.

• 정적 카운트 변수를 가져옵니다.

• 헤드가 NULL이면 아무것도 반환하지 않습니다.

• tmp=head->next

  를 선택하세요.

• searchNthLast(tmp, n1, nlast)를 호출하여 마지막 노드까지 재귀적으로 탐색합니다.

• 그 후 1씩 증가합니다.

• count가 n1과 같으면 *nlast=head를 설정합니다.

• 마지막에 nlast가 가리키는 노드의 값을 결과로 출력합니다.

예시

#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