재귀적 방법을 사용하여 C++의 마지막 연결 리스트에서 n번째 노드를 찾습니다.

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

먼저 목록의 마지막 노드까지 순회하고 재귀(역추적) 증분 카운트에서 돌아올 때입니다. count가 N과 같으면 현재 노드에 대한 포인터가 결과로 반환됩니다.

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

Input- 목록: - 1 → 5 → 7 → 12 → 2 → 96 → 33 N=3

Output− 밑에서 N번째 노드

를 다음과 같이 설명하세요. 2

− 세 번째 노드는 2입니다.

Input− 목록: - 12 → 53 → 8 → 19 → 20 →96 → 33 N=8 p>

Output- 노드가 존재하지 않습니다.

설명 - 목록에는 노드가 7개만 있으므로 아래에서 8번째 노드는 있을 수 없습니다.

아래 프로그램에서 사용한 방법은 다음과 같습니다

이 방법에서는 먼저 노드의 끝에 도달합니다. 재귀를 사용하여 목록을 작성하고 역추적하는 동안 정적 카운트 변수를 증가시킵니다. 개수가 입력 N과 같으면 현재 노드 포인터가 반환됩니다.

• int 데이터 부분이 있는 구조체 노드를 선택하고 노드를 다음 포인터로 사용합니다.

  • 구조 노드와 int 데이터 부분을 사용합니다. p>

  • addtohead(Node** head, int data) 함수는 헤드에 노드를 추가하고 단방향 연결 목록을 만드는 데 사용됩니다.

  • 위 함수를 사용하여 헤드가 첫 번째 노드에 대한 포인터인 단방향 연결 목록을 만듭니다.

  • display(노드* 헤드) 함수는 연결된 목록을 처음부터 인쇄하는 데 사용됩니다.

  • N을 양의 정수로 사용합니다.

  • findNode(Node* head, int n1) 함수는 head와 n1에 대한 포인터를 가져오고 마지막 노드에서 n1번째 노드를 찾으면 결과를 인쇄합니다.

  • 마지막부터 n1번째 노드에 대한 포인터로 blast를 가져옵니다.

  • 노드를 찾으려면 searchNthLast(head, n1, &nlast)를 호출하세요.

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

  • 정적 카운트 변수를 사용하세요.

  • head가 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;
  }

  Output

  위 코드를 실행하면 다음과 같은 출력이 생성됩니다

  Linked list is :
  5 4 10 8 15 12 20
  Nth Node from the last is: 12

위 내용은 재귀적 방법을 사용하여 C++의 마지막 연결 리스트에서 n번째 노드를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!