資料結構
網路
關係資料庫管理系統(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 次瀏覽
