链表是连接在一起的元素序列。每个列表都有一个头和一系列节点，每个节点都有当前节点的数据并链接到下一个节点。链表的基本操作是插入、删除、查找和删除。
从排序链表中删除重复项
删除节点的一种方法是使用递归。其思想是将每个节点与其相邻节点进行比较，并删除它们相等的重复节点。
我们的递归调用将返回到下一个节点。因此，对于下一个元素，我们将调用递归函数，例如 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 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 <data <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->4Linked list after: 1->2->3->4
结论
正如我们在递归调用中看到的，我们相信下一次调用能够实现问题其余部分的预期结果。我们刚刚解决了当前的子问题。记住这一点，我们检查是否可以包含当前元素，并将链表的其余部分交给我们的递归调用，并信任它从那时起为我们提供有效的链表。当我们遍历整个链表时，我们的方法的时间复杂度是 O(n)。
以上就是使用递归从已排序的链表中删除重复项的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444207.html
微信扫一扫 
支付宝扫一扫 
