当前位置: 首页 > news >正文

leetcode82:删除排序链表中的重复节点||

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。

示例 1:

输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

示例 2:

输入:head = [1,1,1,2,3]
输出:[2,3]

提示:

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

步骤1:问题定义

给定一个已排序的链表,要求删除所有重复出现的节点,保留链表中每个元素仅出现一次的节点。该链表是单向的,且数据已按升序排列。目标是构造一个不含重复值的链表并返回其头节点。

输入条件

  1. 链表头节点 head
  2. 链表节点数量在 [0, 300] 范围内。
  3. 每个节点的值在 [-100, 100] 之间。

输出条件: 返回一个去除所有重复元素的链表头节点。

边界条件

  • 空链表:head 为空指针,返回 nullptr
  • 所有节点都重复的情况:如 [1, 1, 1, 1],应返回空链表。
  • 链表不含重复元素:如 [1, 2, 3],应返回原链表。

步骤2:解题思路

这道题可以使用“指针遍历”的方法处理重复节点,因为链表已排序,重复的元素会相邻出现。遍历链表,检测连续相同的元素并移除整个重复区域。

具体步骤:
  1. 初始化一个伪头节点 dummy,指向原链表的头节点,方便在 head 本身为重复节点时处理边界情况。
  2. 定义两个指针:
    • prev:指向已检查并不包含重复的最后一个节点。
    • current:用于遍历链表。
  3. 遍历链表,检查 current 与其后一个节点的值是否相同:
    • 如果相同,继续遍历直到找到最后一个相同的节点。
    • 如果不相同,将 prevnext 指针跳过整个重复区域。
  4. 如果 currentcurrent->next 不相同,直接移动 prevcurrent
  5. 最后,返回 dummy->next 作为新的链表头。
算法复杂度:
  • 时间复杂度O(n),其中 n 是链表节点数量。遍历每个节点最多一次。
  • 空间复杂度O(1),只使用了有限的指针,无额外的空间需求。

步骤3:代码实现

步骤4:算法启发

通过解决此问题,我们得到了处理有序链表中重复元素的一种高效方法。对于单链表操作,借助伪头节点和双指针的应用使代码更简洁,避免了重复元素头部在链表中的特殊处理。

此外,链表去重是常见的链表操作之一,此题中的逻辑也可以扩展到其他变种链表问题中,例如反转链表或合并排序链表。

步骤5:实际应用

链表去重在数据库、数据处理和通信系统中非常重要。例如,通信系统中可以通过此算法实现数据包的重复检测并去除冗余数据包。具体实现如下:

  • 通信系统中会传输大量数据包,可能出现重复的情况。链表结构能高效追踪数据包顺序及是否重复。
  • 通过上述算法,重复数据包会被跳过,保证数据只被接收或存储一次,降低系统开销。

在实际应用中,这种重复检测和过滤算法广泛应用于金融交易、传感器数据分析、网络流量管理等场景中,以确保数据的准确性和高效传输。

相关文章:

leetcode82:删除排序链表中的重复节点||

给定一个已排序的链表的头 head &#xff0c; 删除原始链表中所有重复数字的节点&#xff0c;只留下不同的数字 。返回 已排序的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,3,4,4,5] 输出&#xff1a;[1,2,5]示例 2&#xff1a; 输入&#xff1a;head [1,1,1,2…...

【C#】使用.net9在C#中向现有对象动态添加属性

在 C# 中向现有对象动态添加属性并不像在 Python 或 JavaScript 中那样容易&#xff0c;因为 C# 是一种强类型语言。 但是&#xff0c;我们可以通过使用一些技术和库来实现这一点&#xff0c;例如扩展方法、字典等。本文将详细介绍如何在 C# 中实现这一点。ExpandoObject 方法 …...

Linux进程信号(信号的产生)

目录 什么是信号&#xff1f; 信号的产生 信号产生方式1&#xff1a;键盘 前台进程 后台进程 查看信号 signal系统调用 案例 理解进程记录信号 软件层面 硬件层面 信号产生方式2:指令 信号产生方式3:系统调用 kill系统调用 案例 其他产生信号的函数调用 1.rais…...

97_api_intro_imagerecognition_pdf2word

通用 PDF OCR 到 Word API 数据接口 文件处理&#xff0c;OCR&#xff0c;PDF 高可用图像识别引擎&#xff0c;基于机器学习&#xff0c;超精准识别率。 1. 产品功能 通用识别接口&#xff1b;支持中英文等多语言字符混合识别&#xff1b;formdata 格式 PDF 文件流传参&#xf…...

【算法】【优选算法】二分查找算法(上)

目录 一、二分查找简介1.1 朴素二分模板1.2 查找区间左端点模版1.3 查找区间右端点模版 二、leetcode 704.⼆分查找2.1 二分查找2.2 暴力枚举 三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置3.1 二分查找3.2 暴力枚举 四、35.搜索插⼊位置4.1 二分查找4.2 暴力枚…...

springboot初体验

目录 环境 controller 修改端口号 更改banner图标 运行结果 最核心的:自动装配 环境 jdk17springboot3.3.5maven3.8.2 controller controller层和启动类同级 package com.example.demo.controller; ​ import org.springframework.web.bind.annotation.RequestMapping;…...

使用kalibr_calibration标定相机(realsense)和imu(h7min)

vslam-evaluation/VINS/Installation documentation/4.IMU和相机联合标定kalibr_calibration.md at master DroidAITech/vslam-evaluation GitHub 目录 1.kalibr安装 1.1安装依赖项 1.2创建工作空间 1.3下载kalibr并编译 1.4设置环境变量 2.准备标定板 3.配置驱动和打…...

绿色工厂认定流程

以下是认定绿色工厂的一般流程&#xff1a; 编制年度创建计划 各省辖市、省直管县&#xff08;市&#xff09;会结合本地区重点产业发展现状&#xff0c;挑选一批基础条件良好、有创建意愿和条件的企业进行储备培育&#xff0c;并依据当地工业企业发展实际情况按年度制定绿色工…...

《Python游戏编程入门》注-第5章5

《Python游戏编程入门》的“Analog Clock示例程序”部分讲解了模拟时钟的实现方法。该模拟时钟可以通过时针、分针和秒针的旋转,显示当前时间,如图1所示。 图1 模拟时钟 1 绘制圆 从图1中可以看出,时钟的边缘是一个白色的圆,可以通过如图2所示的代码进行绘制。 图2 绘制圆…...

LangChain Ollama实战文献检索助手(二)少样本提示FewShotPromptTemplate示例选择器

本期是用样例来提示大模型生成我们想要的答案。即在输入中给定提示的样例&#xff0c;以及提示模板&#xff0c;然后匹配较相关的样例进行文献综述。 创建示例样本FewShotPromptTemplate 这里我用GTP-o1生成了几个回答&#xff0c;作为样本 samples [{"theme": &…...

K倍区间 C++

1230. K倍区间 - AcWing题库 一开始想到的用前缀和来做&#xff0c;时间复杂度为O(n^2),Time Limit Exceeded #include <iostream> #include <cstring> #include <algorithm> #include <cstdio>using namespace std;const int N 100010;int n,k; in…...

Linux - 弯路系列3:安装和编译libvirt-4.5.0

系统&#xff1a;Anolis8&#xff08;离线&#xff09; 目录 1、步骤2、make过程中的错误错误1&#xff1a;error: xdr_u_int64_t undeclared (first use in this function) 3、make install的错误错误1&#xff1a;/usr/bin/mkdir -p ""/usr/local/etc/libvirt/nwf…...

Jenkins插件使用问题总结

Git Push插件 插件介绍 主要是用于git推送代码到远程仓库中使用&#xff0c;插件地址 pipeline中使用 官方说明中只有一句代码gitPush(gitScm: scm, targetBranch: env.BRANCH_NAME, targetRepo: origin) 流水线语法中也做的不齐全所以一开始我老是设置错&#xff0c;导致代…...

u盘怎么重装电脑系统_u盘重装电脑系统步骤和详细教程【新手宝典】

u盘怎么重装电脑系统&#xff1f;一个u盘怎么重装电脑系统呢&#xff0c;需要将u盘制作成u盘启动盘pe&#xff0c;然后通过U盘启动盘进入pe进行安装系统&#xff0c;下面小编就教大家u盘重装电脑系统步骤和详细教程。 u盘启动是什么意思&#xff1f; U盘启动盘是一种具有特殊功…...

Sql server查询数据库表的数量

SELECT count(*) FROM sys.objects WHERE typeU --统计表数量 SELECT NAME FROM sys.objects WHERE typeU --列出表名称 或者 SELECT COUNT(*) FROM SysObjects Where XTypeU --统计表数量 SELECT Name FROM SysObjects Where XTypeU --列出表名称 --判断字…...

Linux学习笔记之软件包管理RPM与YUM

RPM包的管理 介绍 RPM&#xff08;RedHat Package Manager&#xff09;用于互联网下载包的打包及安装工具&#xff0c;它包含在某些Linux分发版中。他生成具有.RPM扩展名的文件。RPM类似Windows的setup.exe&#xff0c;这一文件格式虽然打上了RedHat的标志&#xff0c;但理念…...

15分钟学 Go 第 41 天:中间件的使用

第41天&#xff1a;中间件的使用 目标&#xff1a;学习如何在Go语言的Web服务中使用中间件 中间件&#xff08;Middleware&#xff09;是Web开发中的一种常见设计模式&#xff0c;通常用于处理请求和响应过程中的一些共通功能。比如&#xff1a;日志记录、认证授权、请求处理…...

《Python 与 SQLite:强大的数据库组合》

《Python 与 SQLite&#xff1a;强大的数据库组合》 一、Python 与 SQLite 的结合二、安装与连接&#xff08;一&#xff09;安装 SQLite 模块&#xff08;二&#xff09;连接到数据库 三、数据库操作&#xff08;一&#xff09;创建表格&#xff08;二&#xff09;插入数据&am…...

Golang | Leetcode Golang题解之第552题学生出勤记录II

题目&#xff1a; 题解&#xff1a; const mod int 1e9 7type matrix [6][6]intfunc (a matrix) mul(b matrix) matrix {c : matrix{}for i, row : range a {for j : range b[0] {for k, v : range row {c[i][j] (c[i][j] v*b[k][j]) % mod}}}return c }func (a matrix) p…...

Vue3 常用代码指南手抄,超详细 cheatsheet

一、Vue3 基础 1.1 创建 Vue3 项目 使用 Vite 创建 npm create vitelatest my-vue-app -- --template vue cd my-vue-app npm install npm run dev使用 Vue CLI 创建 npm install -g vue/cli vue create my-vue-app1.2 项目结构 my-vue-app ├── node_modules ├── pu…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...