資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用遞迴從已排序的連結串列中刪除重複元素
連結串列是由連線在一起的一系列元素組成的。每個連結串列都有一個頭節點和一系列節點，每個節點都包含當前節點的資料和指向下一個節點的連結。連結串列的基本操作包括插入、刪除、查詢和刪除。
從已排序的連結串列中刪除重複元素
一種刪除節點的方法是使用遞迴。其思想是將每個節點與其相鄰節點進行比較，如果它們相等則刪除重複的節點。
我們的遞迴呼叫將返回下一個節點。因此，對於下一個元素，我們將呼叫我們的遞迴函式，例如 `current_node->next = our_function(node->next)`。
我們相信我們的遞迴函式能夠確保 `current_node->next` 現在包含一個不包含任何重複元素的連結串列。
在主方法中，我們從頭開始構建連結串列，如下所示：
Node* head = new Node(5); head->next = new Node(5); head->next->next = new Node(6); head->next->next->next = new Node(7); head->next->next->next->next = new Node(7); head->next->next->next->next->next = new Node(7);
演算法
該方法使用遞迴從已排序的連結串列中刪除重複元素的過程如下所示。
**步驟 1** - 建立一個所有值按順序排序的連結串列。
**步驟 2** - 如果連結串列不存在，則程式終止。
**步驟 3** - 如果連結串列存在，則將頭節點的下一個節點的值與頭節點的值進行比較。如果這兩個值相同，則刪除頭節點。
**步驟 4** - **_遞迴執行步驟 3_**，將每個節點都視為頭節點，直到連結串列刪除所有重複值。
**步驟 5** - 得到的結果是一個包含不同值的已排序連結串列。
示例
例如，我們有一個已排序的連結串列，其值如下：
1->1->1->2->3->3->4
讓我們來看一個 C++ 程式，它將使用遞迴從上述已排序連結串列中刪除重複元素：
#include <iostream> using namespace std; class Node { public: int data; Node* next; Node(int data) { this->data = data; next = NULL; } }; Node* solve(Node* head) { if (head == NULL) return NULL; head->next = solve(head->next); if (head->next != NULL && head->next->data == head->data) { Node* temp = head->next; delete head; return temp; } return head; } void printList(Node* node) { while (node != NULL) { cout << node->data << (node->next == NULL ? "" : "->"); node = node->next; } } int main() { Node* head = new Node(1); head->next = new Node(1); head->next->next = new Node(1); head->next->next->next = new Node(2); head->next->next->next->next = new Node(3); head->next->next->next->next->next = new Node(3); head->next->next->next->next->next->next = new Node(4); cout << "Linked list before: "; printList(head); head = solve(head); cout << "\nLinked list after: "; printList(head); return 0; }
之後，我們檢查是否將當前節點包含到連結串列中。如果從 `current_node->next` 獲取的滿足條件的連結串列與該節點的值相同，則我們不包含它；否則，我們包含它。
**注意** - 噹噹前節點為 NULL 時，我們返回遞迴的基本條件。
輸出
Linked list before: 1->1->1->2->3->3->4 Linked list after: 1->2->3->4
結論
正如我們在遞迴呼叫中看到的，我們相信下一個呼叫將為問題的其餘部分實現所需的結果。我們只是解決了我們當前的子問題。記住這一點，我們檢查是否可以包含當前元素，並將連結串列的其餘部分傳遞給我們的遞迴呼叫，並相信它會從那時起為我們提供一個有效的連結串列。當我們遍歷整個連結串列時，我們的方法的時間複雜度為 O(n)。
464 次瀏覽
