C++中使用递归查找链表中倒数第n个节点


给定一个单链表和一个正整数N作为输入。目标是使用递归在给定列表中找到从末尾开始的第N个节点。如果输入列表的节点为a → b → c → d → e → f,并且N为4,则从末尾开始的第4个节点将为c。

我们首先遍历到列表的最后一个节点,并在从递归返回(回溯)时递增计数。当计数等于N时,返回指向当前节点的指针作为结果。

让我们看看这种情况下的各种输入输出场景 -

输入 - 列表:1 → 5 → 7 → 12 → 2 → 96 → 33 N=3

输出 - 从最后一个节点开始的第N个节点是:2

解释 - 倒数第3个节点是2。

输入 - 列表:12 → 53 → 8 → 19 → 20 → 96 → 33 N=8

输出 - 节点不存在。

解释 - 列表只有7个节点,因此不可能有第8个最后一个节点。

下面程序中使用的方案如下

在这种方法中,我们将首先使用递归到达列表的末尾,并在回溯时递增一个静态计数变量。一旦计数等于输入N,则返回当前节点指针。

  • 使用int数据部分和Node作为下一个指针的结构Node。

  • 函数addtohead(Node** head, int data)用于将节点添加到头部以创建单链表。

  • 使用上述函数创建单链表,其中head为指向第一个节点的指针。

  • 函数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为第一个节点。

  • 取一个静态计数变量。

  • 如果head为NULL,则不返回任何内容。

  • 取tmp=head->next。

  • 调用searchNthLast(tmp, n1, nlast)递归遍历到最后一个节点。

  • 之后将计数加1。

  • 如果计数等于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

更新于: 2021年11月3日

445 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告