数据结构
网络
关系数据库管理系统 (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 次浏览
