(链表专题) 83. 删除排序链表中的重复元素 ——【Leetcode每日一题】

news/2024/4/17 10:23:09

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。

示例 1:

在这里插入图片描述

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

示例 2:

在这里插入图片描述

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

提示:

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

思路:

法一:一次遍历

由于给定的链表是排好序的,因此重复的元素在链表中出现的位置是连续的,因此我们只需要对链表进行一次遍历,就可以删除重复的元素。

  • 我们从指针 tem 指向链表的头节点,随后开始对链表进行遍历。
  • 如果当前 temtem.next 对应的元素相同,那么我们就将 tem.next从链表中移除;
  • 否则说明链表中已经不存在其它与 tem 对应的元素相同的节点,因此可以将 temr 指向 tem.next

注意下面 C++代码中并没有释放被删除的链表节点的空间。如果在面试中遇到本题,读者需要针对这一细节与面试官进行沟通。

法二:递归

链表具有天然的递归性,链表看成其头节点后挂接一个更短的链表,这个更短的链表看成其头节点后面挂接一个更更短的链表,依次类推。因此本题可以按照如下步骤处理:

  • 删除更短链表中所有重复的元素;
  • 判断原链表的头节点的值是否等于经过第 1 步处理后的更短链表头节点的值;
  • 若相等,则返回更短的链表;
  • 否则,将更短的链表挂接在原链表的头节点的后面,再返回。

代码:(Java、C++)

法一:一次遍历
Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode tem = head;while(tem != null && tem.next != null){if(tem.next.val == tem.val) {tem.next = tem.next.next;}else{tem = tem.next;}}return head;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {ListNode* tem = head;while(tem != NULL && tem->next != NULL){if(tem->next->val == tem->val) {tem->next = tem->next->next;}else{tem = tem->next;}}return head;}
};

法二:递归
Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) {//尾删法if(head == null || head.next == null){return head;}head.next = deleteDuplicates(head.next);return head.val == head.next.val ? head.next : head;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(head == NULL || head->next == NULL){return head;}head->next = deleteDuplicates(head->next);return head->val == head->next->val ? head->next : head;}
};

运行结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度O(n)O(n)O(n),其中 n 是链表的长度
  • 空间复杂度O(1)O(1)O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/42488.html

相关文章

4款【新概念APP】对比+免费下载

4款【新概念APP】对比免费下载4款【新概念APP】对比免费下载新概念英语咖&#xff08;体积小、无广告、全免费、不能倍速播放&#xff09;新概念英语全册&#xff08;免费&#xff0c;但强制广告&#xff0c;否则不能播放音频。可以倍速&#xff09;新概念英语全四册&#xff0…

Redis7持久化

一、redis持久化 1、RDB RDB持久性以指定的时间间隔执行数据集的时间点快照 也就是说在一定的时间间隔内&#xff0c;将某一时刻的数据和状态以文件的形式写到磁盘上&#xff0c;这个快照文件交dump.rdb Redis6更新策略 Redis7更新策略 RDB手动触发 5秒2次修改 RDB手动触…

Qt下载以及调试

1.概念 Qt是一个跨平台的基于C图形用户界面应用程序框架。 常见GUI&#xff1a; Qt&#xff1a;支持多平台&#xff1b;支持css&#xff1b;面向对象特性体现突出&#xff1b;发展趋势良好&#xff1b; MFC&#xff1a;仅在Windows&#xff1b;运行程序效率高&#xff1b;库安…

Openlayers(五)点位聚合Cluster

Openlayers&#xff08;五&#xff09;点位聚合Cluster 1.业务问题 由于点位在地图上显示过多&#xff0c;会造成页面卡顿、点位标注信息相互叠加导致看不清 优化后效果 不断放大层级 2.聚合类Cluster OpenLayers 中聚合是通过 ol.source.Cluster 实现&#xff0c;聚合的原…

纷享销客张睿:快消数字化新时代,数“智”引领新增长

4月6日&#xff0c;在2023年&#xff08;第八届&#xff09;中国快消品创新大会主论坛上&#xff0c;纷享销客经营副总裁兼快消行业部总经理张睿作为嘉宾出席&#xff0c;并以《快消数字化新时代&#xff0c;数“智”引领新增长》为题发表了演讲。他有20余年的市场营销、销售及…

计及需求侧响应日前、日内两阶段鲁棒备用优化【IEEE6节点】(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

Assets--unity资源映射

参考文章&#xff1a; 浅谈Assets——Unity资源映射 - UWA问答 | 博客 | 游戏及VR应用性能优化记录分享 | 侑虎科技 (uwa4d.com) 什么是Assets Assets目录 Assets Unity工程实际的资源目录&#xff0c;所有项目用到的资源、代码、配置、库等原始资源只有放置在这个文件夹才会…

Java 进阶(5) Java IO流

⼀、File类 概念&#xff1a;代表物理盘符中的⼀个⽂件或者⽂件夹。 常见方法&#xff1a; 方法名 描述 createNewFile() 创建⼀个新文件。 mkdir() 创建⼀个新⽬录。 delete() 删除⽂件或空⽬录。 exists() 判断File对象所对象所代表的对象是否存在。 getAbsolute…

google账号注册流程升级了!2023年谷歌gmail邮箱帐号注册申请教程(完整版)

google账号注册升级了&#xff01; 2023年4月份google账号注册流程升级了&#xff0c;升级之前的版本是完成验证手机号码后才填写用户资料&#xff0c;升级之后的版本是需要先填写用户资料才能注册谷歌gmail邮箱帐号&#xff1b; 2023年谷歌gmail邮箱帐号注册申请教程 1、打开…

判断完全二叉树(层序遍历)| C

层序遍历 基本思路&#xff1a;利用队列&#xff0c;出上一层&#xff0c;带下一层&#xff08;NULL不入队列&#xff09; &#xff08;C语言需要自己构建队列→【队列】&#xff1c;用链表实现队列&#xff1e; | [数据结构] | C语言&#xff09; 代码 #include "Queu…

下载和阅读Android源码

目录一、如何下载AOSP1.全量下载2.单个下载目录结构二、如何阅读AOSP1.要阅读哪些源码2.阅读源码的顺序和方式2.1 阅读顺序2.2 阅读方式3.用什么工具来阅读3.1 下载安装Source Insight3.2 导入AOSP源码3.3查看源码三、其他一、如何下载AOSP 源码下载是我们分析源码的开始&…

GEE:Gmeans

G-means是一种聚类算法,它是基于K-means算法的改进版本。K-means算法的一个主要缺点是需要事先指定聚类的数量,而G-means算法则可以自动确定聚类的数量。 G-means算法使用了类似于K-means的迭代过程,但在每次迭代时,它会检查每个聚类是否可以继续细分为两个子聚类。这个检…

item_search_img-按图搜索1688商品(拍立淘)接口的接入参数说明

参数说明 通用参数说明 version:API版本key:调用key,测试key:test_api_keyapi_name:API类型[item_get,item_search]cache:[yes,no]默认yes&#xff0c;将调用缓存的数据&#xff0c;速度比较快result_type:[json,xml,serialize,var_export]返回数据格式&#xff0c;默认为jsonl…

如何处理后端返回的复杂数据

将接口的复杂数据结构映射成简单的数据结构 假设我们有一个API&#xff0c;返回以下数据&#xff1a; {"id": 1,"name": "Example API","process_params": {"param1": {"name": "Parameter 1","…

赶紧收藏!网上疯传的150个ChatGPT「超级提问模型」,都在这里了

这是自 ChatGPT大爆发以来&#xff0c;全网&#xff08;国内外&#xff09;收录的150个&#xff0c;已经被成功验证、测试最多的「超级提问模型」。 这150个模型&#xff0c;在站外Github上&#xff0c;被超过1000w人用来学习、体验如何向 ChatGPT 提问。 它们是一个个&#…

企业级信息系统开发讲课笔记2.4 利用MyBatis实现条件查询

文章目录零、本节学习目标一、查询需求二、打开MyBatisDemo项目三、对学生表实现条件查询&#xff08;一&#xff09;创建学生映射器配置文件&#xff08;二&#xff09;在MyBatis配置文件里注册学生映射器配置文件&#xff08;三&#xff09;创建学生映射器接口&#xff08;四…

关于【无人驾驶航空器飞行管理暂行条例】对航模的一些信息讨论汇总

关于【无人驾驶航空器飞行管理暂行条例】对航模的一些信息讨论&汇总1. 源由2. 讨论3. 理解3.1 关于“管理对象”的理解3.2 关于“模型航空器管理规则”的理解3.3 关于“模型航空器”的理解3.4 关于“安全”的理解4. 参考资料1. 源由 早在2018年之前&#xff0c;业界已经提…

项目打包发布流程

---》》》项目打包发布 1.编译并构建项目 2.部署 npm i npm run build scp2&#xff1a;需要写代码 ---》》》 后续有空更新&#xff1a;赋几个链接&#xff1a; Jenkins官网 nullhttps://www.jenkins.io/zh/一文详解Jenkins的安装与配置Jenkins是一个基于Java开发的开源…

接入丰桥,下单到打印面单到配送开发流程

顺丰开放平台地址&#xff1a;顺丰开放平台 一、了解官网 1.1、开发文档 开发接口之前可以先查看熟悉文档&#xff0c;尤其是API文档仔细阅读。进入之后是如下图&#xff0c;根据自己需要开发的接口&#xff0c;先查看文档&#xff0c;然后根据文档要求来请求并处理响应。 1.2…

家政服务小程序实战开发教程017-我的页面未注册功能开发

顾客在家政服务小程序可以在线提交预约信息&#xff0c;预约成功后可以查看订单的进度。我们本篇就来实现一下我的页面的功能。 1 新建页面 进入编辑器&#xff0c;在组件页面区域点击号&#xff0c;创建我的页面 2 未登录页面开发 我的页面的逻辑是如果用户未注册&#…
最新文章