단일 연결된 목록과 양의 정수 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번째 마지막 노드에 대한 포인터를 반환하며, 헤드가 첫 번째 노드입니다.
정적 카운트 변수를 사용하세요.
tmp=head->next를 선택하세요.
마지막 노드까지 재귀적으로 순회하려면 searchNthLast(tmp, n1, nlast)를 호출하세요.
이후 개수가 1씩 증가합니다.
count가 n1과 같아지면 *nlast=head를 설정하세요.
마지막으로 nlast가 가리키는 노드의 값을 결과로 출력합니다.
#includeusing 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< 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 :"< 로그인 후 복사
위 코드를 실행하면 다음과 같은 출력이 생성됩니다
Linked list is : 5 4 10 8 15 12 20 Nth Node from the last is: 12
위 내용은 재귀적 방법을 사용하여 C++의 마지막 연결 리스트에서 n번째 노드를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!