在C++中递归插入和遍历链表

我们得到了用于形成链表的整数值。任务是使用递归方法先插入然后遍历单链表。

在末尾递归添加节点

• 如果 head 为 NULL → 将节点添加到 head

• 否则添加到 head( head → next )

递归遍历节点

• 如果 head 为 NULL → 退出

• 否则打印( head → next )

示例

输入− 1 - 2 - 7 - 9 - 10

输出

输出 strong>− 链表：1 → 2 → 7 → 9 → 10 → NULL

输入− 12 - 21 - 17 - 94 - 18

输出− 链表：12 → 21 → 17 → 94 → 18 → NULL

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

在这种方法中，我们将使用函数添加节点并遍历单链表并递归调用它们以进行下一个输入。

• 采用带有整数和下一个指针 SLLNode* 的结构体 SLLNode 。

• 函数 addtoEnd(SLLNode* head, int data) 获取指向链表头的指针和数据部分的整数，并将节点添加到链表的末尾。

  li>

• 如果头指针为 NULL，则列表为空，现在添加一个新节点并将其设置为头。将 head → next 添加为 NULL。返回指向该节点的指针

• 如果 head 不为 null，则使用 head->next = addtoEnd(head->next, data) 将节点添加到 head → next。

• 函数 traverseList(SLLNode* head) 从 head 开始遍历并打印每个值。

• 如果 head 为 NULL，则打印 NULL 并返回.

• 否则打印数据值并使用 traverseList(head->next) 遍历下一个。

• 在主创建列表中使用addtoEnd() 并使用 traverseList() 打印列表。

示例

#include <bits/stdc++.h>
using namespace std;
struct SLLNode {
   int data;
   SLLNode* next;
};
SLLNode* addtoEnd(SLLNode* head, int data){
   if (head == NULL){
      SLLNode *nodex = new SLLNode;
      nodex->data = data;
      nodex->next = NULL;
      return nodex;
   }
   else{
      head->next = addtoEnd(head->next, data);
    }
   return head;
}
void traverseList(SLLNode* head){
   if (head == NULL){
      cout <<"NULL";
      return;
   }
   cout << head->data << " -> ";
   traverseList(head->next);
}
int main(){
   SLLNode* head1 = NULL;
   head1 = addtoEnd(head1, 1);
   head1 = addtoEnd(head1, 8);
   head1 = addtoEnd(head1, 56);
   head1 = addtoEnd(head1, 12);
   head1 = addtoEnd(head1, 34);
   cout<<"Linked List is :"<<endl;
   traverseList(head1);
   return 0;
}

输出

如果我们运行上述代码，将会生成以下输出

Linked List is :
1 -> 8 -> 56 -> 12 -> 34 -> NULL

以上是在C++中递归插入和遍历链表的详细内容。更多信息请关注PHP中文网其他相关文章！