使用遞歸從已排序的鍊錶中刪除重複項

鍊錶是連接在一起的元素序列。每個列表都有一個頭和一系列節點，每個節點都有當前節點的資料並連結到下一個節點。鍊錶的基本操作是插入、刪除、尋找和刪除。

從排序鍊錶中刪除重複項

刪除節點的一種方法是使用遞歸。其想法是將每個節點與其相鄰節點進行比較，並刪除它們相等的重複節點。

我們的遞歸呼叫將會回到下一個節點。因此，對於下一個元素，我們將呼叫遞歸函數，例如 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;
}

之後，我們檢查是否將目前節點包含到鍊錶中。如果我們從目前節點->下一個節點得到的滿足鍊錶與該節點具有相同的值，則不包含該節點；否則，我們將包括在內。

注意 - 當目前節點為 NULL 時，我們傳回遞歸的基本條件。

輸出

Linked list before: 1->1->1->2->3->3->4
Linked list after: 1->2->3->4

結論

正如我們在遞歸呼叫中所看到的，我們相信下一次呼叫能夠實現問題其餘部分的預期結果。我們剛剛解決了當前的子問題。記住這一點，我們檢查是否可以包含當前元素，並將鍊錶的其餘部分交給我們的遞歸調用，並信任它從那時起為我們提供有效的鍊錶。當我們遍歷整個鍊錶時，我們的方法的時間複雜度是 O(n)。

以上是使用遞歸從已排序的鍊錶中刪除重複項的詳細內容。更多資訊請關注PHP中文網其他相關文章！