数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用递归删除链表
链表
链表是一种线性数据结构，其元素存储在非连续的内存位置。每个元素包含一个节点。一个节点由一个数据字段组成，该字段保存元素的值，以及一个地址字段，该字段指向系列中下一个节点的位置。
链表的第一个节点称为列表的“头”。链表的最后一个元素可以定义为指向NULL的元素。下面显示了链表的图表表示。
问题陈述
给定一个链表，任务是使用递归删除所有元素，即链表的头应为NULL。
解决方案方法
要删除链表的所有元素，我们遍历链表并逐个删除所有节点。当头等于NULL时，链表被认为为空。
算法
该方法包括以下步骤：
如果头等于NULL，则返回
递归删除头节点指向的节点。
删除头节点。
显示答案。
伪代码
类节点()
定义公共变量“data”
定义公共变量“next”
构造函数节点(val)
初始化data = val
初始化next = NULL
函数insert(key)
使用数据值“key”初始化新节点“n”。
如果(head == NULL)
设置head = n
返回
初始化temp = head
当(temp->next != NULL)
temp = temp->next
设置temp->next = n
返回
函数deleteLL()
如果(head == NULL)
返回
函数调用deleteLL(head->next)
free(head)
函数printLL()
初始化temp = head
当(temp != NULL)
打印temp->data
temp = temp->next
返回
干运行
Input: 1 -> 2 -> 3 -> 4 Output: [ ]
说明 - 在将所有节点一个接一个地插入到链表中之后，链表可以表示为
当使用此列表的头（即节点1）调用deleteLL()函数时，它首先检查head是否为NULL。由于它不是，它会使用列表中的下一个节点（即节点2）调用自身。
对deleteLL()的第二次调用检查当前头（即节点2）是否为NULL。由于它不是，它会使用列表中的下一个节点（即节点3）调用自身。
类似地，它会使用节点4调用自身。在此之后，在下一个调用中，head = NULL，因为我们已经到达链表的末尾。因此，函数返回到链表中的先前调用并释放当前头节点。
简单来说，节点的删除顺序相反：4 -> 3 -> 2 -> 1。
示例：C++程序
下面的C++程序使用insert()函数逐个将一系列节点插入到链表中。然后，它使用函数printLL()打印原始列表。之后，它通过递归调用函数deleteLL()删除列表的所有节点。它以相反的顺序删除节点。然后它将head赋值为NULL。最后，它使用函数printLL()打印空链表。
下面的C++程序递归地删除给定的链表：
#include <bits/stdc++.h>
using namespace std;
// A linked list node class. Each node consists of a data field and an address field.
class node {
public:
int data;
node *next;
node(int val){
data = val;
next = NULL;
}
};
// This function inserts a node to form a linked list.
// We push a new node to the end of the list if the head of the linked list is given.
void insert(node *&head, int key){
node *n = new node(key);
if (head == NULL){
head = n;
return;
}
node *temp = head;
while (temp->next != NULL){
temp = temp->next;
}
temp->next = n;
return;
}
// This function recursively deletes all the nodes of the linked list one by one.
void deleteLL(node *&head) {
if (head == NULL){
return;
}
deleteLL(head->next);
free(head);
}
// This function prints all the nodes of the linked list.
void printLL(node *head) {
node* temp = head;
while (temp != NULL){
cout << temp->data << " ";
temp = temp->next;
}
}
// Driver function
int main(){
node *head = NULL;
insert(head, 1);
insert(head, 2);
insert(head, 30);
insert(head, 4);
insert(head, 5);
insert(head, 60);
cout << "Original Linked List: ";
printLL(head); // 1 2 30 4 5 60
cout << "Linked List after Deletion: ";
deleteLL(head);
// after we free(head), it now points to an illegal location
// so we set head equal to NULL
head = NULL;
printLL(head); // empty linked list
return 0;
}
输出
Original Linked List: 1 2 30 4 5 60 Linked List after Deletion:
时间和空间复杂度分析
时间复杂度：O(n)
insert()函数的时间复杂度为O(n)，因为它遍历链表以找到末尾。
printLL()函数的时间复杂度为O(n)，因为它也遍历整个链表。
递归删除链表的deleteLL()函数的时间复杂度为O(n)，因为它访问每个节点一次。
空间复杂度：O(n)
insert()函数的空间复杂度为O(1)，因为它不需要任何额外空间。
此外，printLL函数也不使用额外的空间，因此其空间复杂度为O(1)。
deleteLL()函数是一个递归函数，它使用调用栈来跟踪要删除的节点。调用栈的最大深度将等于链表中的节点数。因此，deleteLL函数的空间复杂度为O(n)。
因此，代码的整体空间复杂度为O(n)。
结论
链表可以用来实现像栈、队列和哈希表这样的数据结构。它们是有用的数据结构，可以被认为是动态数组。本文讨论了删除链表的递归方法。它详细解释了链表的概念、递归解决方案的方法以及C++程序代码、干运行和时间和空间复杂度分析。
966 次浏览
