使用递归方法在C++中找到链表倒数第n个节点-C++-PHP中文网

使用递归方法在C++中找到链表倒数第n个节点

WBOY

发布： 2023-09-15 17:53:05

转载

1431人浏览过

使用递归方法在c++中找到链表倒数第n个节点

给定一个单链表和正整数 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)用于打印从头开始的链表
  
  黑点工具
  在线工具导航网站，免费使用无需注册，快速使用无门槛。
  
  18
  
  查看详情
- 取 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 <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
```
登录后复制