递归方法在C++中从链表的末尾找到第n个节点
给定一个单向链表和正整数N作为输入。目标是使用递归从给定列表的末尾找到第N个节点。如果输入列表有节点a→b→c→d→e→f并且N是4，那么从末尾算起的第4个节点将是c。
我们将首先遍历到列表中的最后一个节点，同时从递归（回溯）增量计数返回。当count等于N时，返回指向当前节点的指针作为结果。
让我们看看这个的各种输入输出场景-
输入 -列表：-1→5→7→12→2→96→33N=3
输出 -最后的第N个节点是：2
说明 -倒数第三个节点是2。
输入 -列表：-12→53→8→19→20→96→33N=8
输出 -节点不存在。
说明-该列表只有7个节点，因此不可能有第8个节点。
下面程序中使用的方法如下
在这种方法中，我们将首先使用递归到达列表的末尾，在回溯时我们将增加一个静态计数变量。一旦count等于输入N，就返回当前节点指针。
取结构体Node与int数据部分和Node作为下一个指针。
函数addtohead(Node**head,intdata)用于向头部添加节点以创建单向链表。
使用上述函数创建一个单向链表，将head作为指向第一个节点的指针。
函数display(Node*head)用于打印从头节点开始的链表。
取N为正整数。
函数findNode(Node*head,intn1)获取指向head和n1的指针，并在找到从末尾开始的第n1个节点时打印结果。
将blast作为指向末尾第n1节点的指针。
调用searchNthLast(head,n1,&nlast)来查找该节点。
函数searchNthLast(Node*head,intn1,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 << "从最后的第N个节点是： "<< 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<<"链表是："<<endl;
display(head);
cout<<endl;
findNode(head, N);
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
链表是： 5 4 10 8 15 12 20 从最后的第N个节点是： 12