使用递归从已排序的链表中删除重复项

阿枫大大_5610

阿枫大大_5610

2023-09-01

967人浏览

转载

使用递归从已排序的链表中删除重复项

链表是连接在一起的元素序列。每个列表都有一个头和一系列节点,每个节点都有当前节点的数据并链接到下一个节点。链表的基本操作是插入、删除、查找和删除。

从排序链表中删除重复项

删除节点的一​​种方法是使用递归。其思想是将每个节点与其相邻节点进行比较,并删除它们相等的重复节点。

我们的递归调用将返回到下一个节点。因此,对于下一个元素,我们将调用递归函数,例如 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 - 如果链表确实存在,则将头节点的下一个值与头节点中的值进行比较。如果两个值相同,则删除头部。

    手机移动端多图片上传删除js代码
    手机移动端多图片上传删除js代码

    手机移动端多图片上传删除js代码,因multiple在安卓手机中不兼容,所以在安卓上只能一次选中一张图片,在iOS系统上可以实现多图片的上传。

    下载
  • 第 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 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 <p>之后,我们检查是否将当前节点包含到链表中。如果我们从当前节点->下一个节点得到的满足链表与该节点具有相同的值,则不包含该节点;否则,我们将包括在内。</p>
<p><b>注意</b> - 当当前节点为 NULL 时,我们返回递归的基本条件。</p>
<h2>输出</h2>
<pre class="brush:php;toolbar:false;">Linked list before: 1->1->1->2->3->3->4
Linked list after: 1->2->3->4

结论

正如我们在递归调用中看到的,我们相信下一次调用能够实现问题其余部分的预期结果。我们刚刚解决了当前的子问题。记住这一点,我们检查是否可以包含当前元素,并将链表的其余部分交给我们的递归调用,并信任它从那时起为我们提供有效的链表。当我们遍历整个链表时,我们的方法的时间复杂度是 O(n)。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
c语言中null和NULL的区别
c语言中null和NULL的区别

c语言中null和NULL的区别是:null是C语言中的一个宏定义,通常用来表示一个空指针,可以用于初始化指针变量,或者在条件语句中判断指针是否为空;NULL是C语言中的一个预定义常量,通常用来表示一个空值,用于表示一个空的指针、空的指针数组或者空的结构体指针。

2023.09.22

569

3

java中null的用法
java中null的用法

在Java中,null表示一个引用类型的变量不指向任何对象。可以将null赋值给任何引用类型的变量,包括类、接口、数组、字符串等。想了解更多null的相关内容,可以阅读本专题下面的文章。

2024.03.01

1698

6

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7216

4

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

80

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Django 教程
Django 教程

共28课时 | 10.1万人学习

【李炎恢】ThinkPHP8.x 后端框架课程
【李炎恢】ThinkPHP8.x 后端框架课程

共50课时 | 6.3万人学习