给定一个单链表和正整数 N 作为输入。目标是使用递归找到给定列表中从末尾算起的第 N 个节点。如果输入列表有节点 a → b → c → d → e → f 并且 N 为 4，那么倒数第 4 个节点将是 c。
我们将首先遍历直到列表中的最后一个节点以及从递归（回溯）增量计数返回时。当 count 等于 N 时，则返回指向当前节点的指针作为结果。
让我们看看此的各种输入输出场景 –
输入– List ： – 1 → 5 → 7 → 12 → 2 → 96 → 33 N=3
输出− 倒数第 N 个节点为：2
立即学习“C++免费学习笔记（深入）”；
解释− 第三个节点是 2。
输入− 列表：- 12 → 53 → 8 → 19 → 20 →96 → 33 N=8 p>
输出– 节点不存在。
说明 – 列表只有 7 个节点，因此不可能有倒数第 8 个节点.
下面的程序中使用的方法如下
在这种方法中，我们将首先使用递归到达列表的末尾，在回溯时我们将增加一个静态计数变量。一旦 count 等于输入 N，就返回当前节点指针。
采用带有 int 数据部分的结构 Node，并将 Node 作为下一个指针。
采用结构 Node 和 int 数据部分。 p>
函数addtohead(Node** head, int data)用于向头部添加节点，创建单向链表。
使用上面的函数创建一个单向链表，头作为指向第一个节点的指针。
函数display(Node* head)用于打印从头开始的链表
取 N 为正整数。
函数 findNode(Node* head, int n1) 获取指向head 和 n1，当找到倒数第 n1 个节点时打印结果。
将blast作为指向倒数第 n1 个节点的指针。
调用 searchNthLast(head, n1, &nlast) 来查找该节点。
函数 searchNthLast(Node* head, int n1, Node** nlast) 返回指向链表中从末尾算起第 n1 个最后一个节点的指针，头为第一个节点。
采用静态计数变量。
如果 head 为 NULL，则不返回任何内容。
取 tmp=head->next。
调用 searchNthLast(tmp, n1, nlast) 递归遍历直到最后一个节点。
之后 count 加 1。
如果 count 变为等于n1则设置*nlast=head。
最后打印nlast指向的节点的值作为结果。
示例
#include 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: "<data; }}void display(Node* head){ Node* curr = head; if (curr != NULL){ cout<data<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 20Nth Node from the last is: 12
以上就是使用递归方法在C++中找到链表倒数第n个节点的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445258.html
微信扫一扫 
支付宝扫一扫 
