当前位置: 首页 > 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…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...