【链表】Leetcode 82. 删除排序链表中的重复元素 II【中等】

news/2024/7/25 21:41:58/文章来源:https://blog.csdn.net/FLGBgo/article/details/139258406

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

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

示例 1:

在这里插入图片描述
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

解题思路

由于链表是已排序的,所以重复的节点会相邻出现。可以使用双指针法来解决这个问题,一个指针用于遍历链表,另一个指针用于跟踪上一个未重复的节点。

  • 遍历链表:使用两个指针pre和current。pre用于指向上一个未重复的节点,current用于遍历链表。
  • 删除重复节点:如果current和current.next的值相等,则继续向前遍历直到遇到不同的值为止。将pre.next指向当前遇到的第一个不同值节点。
  • 移动指针:如果current和current.next的值不同,pre移动到current位置,current继续向前遍历。
  • 返回结果:返回哨兵节点的下一个节点。

Java实现

public class DeleteDuplicates {public static class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}public ListNode deleteDuplicates(ListNode head) {// 创建哨兵节点ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;ListNode current = head;while (current != null) {// 跳过当前节点后面所有的重复节点while (current.next != null && current.val == current.next.val) {current = current.next;}// 如果pre的下一个节点是current,说明当前节点没有重复if (pre.next == current) {pre = pre.next;} else {// 如果pre的下一个节点不是current,说明有重复节点,跳过所有重复节点pre.next = current.next;}current = current.next;}return dummy.next;}public static void main(String[] args) {DeleteDuplicates deleteDuplicates = new DeleteDuplicates();// 创建示例链表 1->2->3->3->4->4->5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(3);head.next.next.next.next = new ListNode(4);head.next.next.next.next.next = new ListNode(4);head.next.next.next.next.next.next = new ListNode(5);// 删除重复节点ListNode newHead = deleteDuplicates.deleteDuplicates(head);printList(newHead); // 输出: 1->2->5}// 辅助方法:打印链表public static void printList(ListNode head) {ListNode current = head;while (current != null) {System.out.print(current.val);if (current.next != null) {System.out.print("->");}current = current.next;}System.out.println();}
}

时间空间复杂度

  • 时间复杂度:O(n),其中 n 是链表的节点数。需遍历链表一次。
  • 空间复杂度:O(1),只使用了几个额外的指针。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1053934.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

代码文本编辑器-小白教程(Sublime text, Notepad++ Acode下载安装与使用)

代码文本编辑器-小白教程(Sublime text, Notepad Acode下载安装与使用) 1. Windows平台和Linux平台1.1 Sublime text1.2 Notepad 2. 安卓平台 Acode参考资料 1. Windows平台和Linux平台 1.1 Sublime text 一、安装教程 1、打开Sublime Text官网下载安…

UE5 UE4 快速定位节点位置

在材质面板中,找到之前写的一个节点,想要修改,但是当时写的比较多,想要快速定位到节点位置. 在面板下方的 Find Results面板中,输入所需节点,找结果后双击,就定位到该节点处。 同理,…

STM32简易音乐播放器(HAL库)

一、设计描述 本设计以STM32MP157A单片机为核心控制器,加上其他的模块一起组成基于单片机的音乐盒的整个系统,通过不同频率的PWM使蜂鸣器播放音乐,通过按键中断实现歌曲切换,音量调节,定时器中断实现播放速度调节&…

小程序自动化辅助渗透脚本(2024)

简介 1.还在一个个反编译小程序吗? 2.还在自己一个个注入hook吗? 3.还在一个个查看找接口、查找泄露吗? 现在有自动化辅助渗透脚本了,自动化辅助反编译、自动化注入hook、自动化查看泄露 注:本工具仅用于学习交流&…

咖啡看书休闲时光404错误页面源码

源码介绍 咖啡看书休闲时光404错误页面源码,源码由HTMLCSSJS组成,记事本打开源码文件可以进行内容文字之类的修改,双击html文件可以本地运行效果,也可以上传到服务器里面,重定向这个界面 源码效果 源码下载 咖啡看书…

基于模糊PID控制器的汽车电磁悬架控制系统simulink建模与仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 5.完整工程文件 1.课题概述 基于模糊PID控制器的汽车电磁悬架控制系统simulink建模与仿真。 2.系统仿真结果 上面的仿真结果是无控制器和LQG的对比,以及有控制器和LQG的对比仿真。 3.核心程…

windows ollama 指定模型下载路径

为Ollama指定模型的下载路径 在Windows系统中&#xff0c;如果想为Ollama指定模型的下载路径&#xff0c;可以通过设置环境变量来实现。以下是详细的步骤&#xff1a; 确定默认下载路径&#xff1a; 默认情况下&#xff0c;Ollama的模型可能会下载到C:\Users\<用户名>…

maven聚合工程整合springboot+mybatisplus遇到的问题

前言&#xff08;可以直接跳过看下面解决方法&#xff09; 项目结构 两个module&#xff1a; yema-terminal-boot 是springboot项目&#xff0c;子包有&#xff1a;controller、service、dao 等等。属于经典三层架构。那么&#xff0c;该module可以理解为是一个单体项目&…

使用nexus搭建的nodejs私库,定期清理无用的npm组件,彻底释放磁盘空间

一、背景 昨天我们整理了一篇关于docker私库&#xff0c;如何定期清理以释放磁盘空间的文章。 虽然也提及了npm前端应用的组件该如何定期清理的&#xff0c;本文是对它作一个补充说明。 前文也看到了&#xff0c;npm组件占用的blob空间为180多GB&#xff0c;急需清理。 二、…

OpenStack创建云主机——超级详细步骤

四、创建云主机 一台云主机成功创建或启动需要依赖OpenStack中的各种虚拟资源&#xff0c;如CPU、内存、硬盘等。如果需要云主机丽娜姐外部网络&#xff0c;还需要网络、路由器等资源。如果需要外部网络访问云主机&#xff0c;那么还需要配置浮动IP。因此&#xff0c;在创建云主…

提升(或降低)插入的内容的位置:\raisebox

\raisebox 是 LaTeX 中的一个命令&#xff0c;用于提升&#xff08;或降低&#xff09;插入的内容&#xff08;如文本、图像等&#xff09;的位置。该命令可以用于调整垂直位置&#xff0c;使内容相对于周围内容上下移动。 语法如下&#xff1a; \raisebox{<distance>}…

C++ | Leetcode C++题解之第118题杨辉三角

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<vector<int>> generate(int numRows) {vector<vector<int>> ret(numRows);for (int i 0; i < numRows; i) {ret[i].resize(i 1);ret[i][0] ret[i][i] 1;for (int j 1; j &…

tinyrenderer-渲染器着色

整理了代码&#xff0c;创建了一个相机类&#xff0c;控制镜头 class Camera { public:Camera(Vec3f cameraPos, Vec3f target, Vec3f up):cameraPos_(cameraPos), target_(target), up_(up) {}Matrix getView();Matrix getProjection(); private:Vec3f cameraPos_;Vec3f targ…

四川汇聚荣聚荣科技有限公司好不好?

在当今科技飞速发展的时代&#xff0c;企业要想在激烈的市场竞争中脱颖而出&#xff0c;必须具备强大的技术实力和良好的市场口碑。那么&#xff0c;作为一家专注于科技创新的公司&#xff0c;四川汇聚荣聚荣科技有限公司究竟如何呢?接下来&#xff0c;我们将从四个方面进行详…

都2024年了!是谁还不会优化 Hive 的小文件啊!!!速看!

文章目录 小文件产生的原因1.查询建表或者插入2.装载数据3.动态分区小文件影响解决方法针对已经存在的小文件进行优化1.小文件归档2.getmerge3.concatenate4.重写针对写入数据时的优化1.调参优化2.动态分区优化3.使用 Spark 算子控制小文件数量查看 HDFS 上的文件时,无意间点进…

Matlab|主动配电网故障恢复与孤岛划分模型【多时段】

目录 1 主要内容 1.1 模型目标 1.2 约束条件 2 部分代码 3 程序结果 4 下载链接 1 主要内容 程序主要方法复现《主动配电网故障恢复的重构与孤岛划分统一模型》&#xff0c;完全复现检修策略约束和潮流约束&#xff0c;辐射状与连通性约束考虑孤岛划分情形&#xff0c;采…

微火问答:全域外卖和本地生活服务是同个项目吗?

当前&#xff0c;本地生活赛道火爆程度不断升级&#xff0c;作为其主要板块之一的团购外卖也持续迸发出新的活力。而全域运营的出现无疑是给团购外卖这把正在熊熊燃烧的烈火&#xff0c;又添了一把新柴&#xff01; 所谓全域运营&#xff0c;简单来说&#xff0c;就是指所有领…

基于SpringBoot设计模式之结构型设计模式·适配器模式

文章目录 介绍开始使用委托的适配器&#xff08;媒体播放器&#xff09;架构图定义被适配者定义需求接口定义适配者 使用继承的适配器&#xff08;手机充电接口&#xff09;架构图定义被适配者定义需求接口定义适配者 测试样例 总结优点缺点 介绍 在程序世界中&#xff0c;经常…

猫耳 WebSocket 跨端优化实践

前言 在现代的移动应用程序中&#xff0c;长连接是一种不可或缺的能力&#xff0c;包括但不限于推送、实时通信、信令控制等常见场景。在猫耳FM的直播业务中&#xff0c;我们同样使用了 WebSocket 长连接作为我们实时通信的基础。 在我们推进用户体验优化的工作中&#xff0c;…

Golang | Leetcode Golang题解之第118题杨辉三角

题目&#xff1a; 题解&#xff1a; func generate(numRows int) [][]int {ans : make([][]int, numRows)for i : range ans {ans[i] make([]int, i1)ans[i][0] 1ans[i][i] 1for j : 1; j < i; j {ans[i][j] ans[i-1][j] ans[i-1][j-1]}}return ans }