【刷题之路】LeetCode 203. 移除链表元素
【刷题之路】LeetCode 203. 移除链表元素
- 一、题目描述
- 二、解题
- 1、方法1——在原链表上动刀子
- 1.1、思路分析
- 1.2、代码实现
- 2、方法2——使用额外的链表
- 2.1、思路分析
- 2.2、代码实现
一、题目描述
原题连接: 203. 移除链表元素
题目描述:
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例 1:
输入: head = [1,2,6,3,4,5,6], val = 6
输出: [1,2,3,4,5]
示例 2:
输入: head = [], val = 1
输出: []
示例 3:
输入: head = [7,7,7,7], val = 7
输出: []
提示:
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
二、解题
1、方法1——在原链表上动刀子
1.1、思路分析
首先我们应该能想到的就是使用一个cur指针来遍历链表,当cur-val == val时就删除cur:

但是这是单链表,也就意味着如果我们直接删除掉cur的话,就找不到cur后面的节点了,所以正确的做法应该是在删除之前先使用一个pre指针保存好cur的前一个节点,删除之前先让pre的next指向cur的next,然后再删除cur:

然后再使cur = pre->next即可。
不过有一个特殊情况就是当第一个节点的val刚好等于待删除的val时,例如:

这时候的cur就没有前驱节点pre了,所以这时候就应该直接执行头删。
而当我们要删除的节点刚好是链表的最后一个节点的时候,这种情况其实并不用特殊处理,因为当我们向上面一样执行完删除操作时,cur就已经为NULL了pre就已经是最后一个节点了:

1.2、代码实现
有了以上思路,那我们写起代码来也就水到渠成了:
struct ListNode* removeElements(struct ListNode* head, int val){if (NULL == head) {return NULL;}struct ListNode *cur = head;struct ListNode *pre = NULL; while (cur) {if (val == cur->val) {if (cur == head) { // 头删head = cur->next;free(cur);cur = head;} else {pre->next = cur->next;free(cur);cur = pre->next;}} else { // 迭代地往后走pre = cur;cur = cur->next;}}return head;
}
时间复杂度;O(n),n为链表的长度。
空间复杂度:O(1),我们只需要用到常数级的额外空间。
2、方法2——使用额外的链表
2.1、思路分析
我们可以创建一个新的链表,用一个新的头指针newhead指向。使用一个cur指针来遍历原链表,当cur的val不等于待删除的val时候,就将cur尾插到新链表中,当cur的val等于待删除的val时就删除cur:

同样的,为了保证删除节点后还能找到下一个节点,我们需要提前使用一个next指针保存cur的下一个节点:

而且插入新链表执行的是尾插,为了不必每次都找尾,我们需要在使用一个指针tail来保存新节点的尾节点:

然后每次的尾插我们就只需要执行tail->next = cur,然后执行tail = tail->next即可。
还有一个特殊情况那就只剩头插了,因为是插入第一个节点,所以此时的tail就为NULL,所以不能直接使用tail,这时候应该直接执行头插,即newhead = cur,然后再让tail = cur即可:

2.2、代码实现
有了以上思路,那我们写起代码来也就水到渠成了:
struct ListNode* removeElements(struct ListNode* head, int val){if (NULL == head) {return NULL;}struct ListNode *cur = head;struct ListNode *newhead = NULL; // 新链表的头指针struct ListNode *Next = NULL; // 当cur->val == val时,保存cur的下一个节点,以辅助释放curstruct ListNode *tail = NULL; // 保存新链表的最后一个节点while (cur) {if (cur->val == val) {Next = cur->next;free(cur);cur = Next;} else {if (NULL == newhead) {newhead = cur;tail = cur;} else {tail->next = cur;tail = tail->next;}cur = cur->next;tail->next = NULL;}}return newhead;
}
相关文章:
【刷题之路】LeetCode 203. 移除链表元素
【刷题之路】LeetCode 203. 移除链表元素 一、题目描述二、解题1、方法1——在原链表上动刀子1.1、思路分析1.2、代码实现 2、方法2——使用额外的链表2.1、思路分析2.2、代码实现 一、题目描述 原题连接: 203. 移除链表元素 题目描述: 给你一个链表的…...
关于Open Shift(OKD) 中 用户认证、权限管理、SCC 管理的一些笔记
写在前面 因为参加考试,会陆续分享一些 OpenShift 的笔记博文内容为 openshift 用户认证和权限管理以及 scc 管理相关笔记学习环境为 openshift v3 的版本,有些旧这里如果专门学习 openshift ,建议学习 v4 版本理解不足小伙伴帮忙指正 对每个…...
活动文章测试(勿删)
大家好! 我是CSDN官方博客! 恭喜你正式加入CSDN博客,迈上技术成神之路~~ 路漫漫其修远兮——身为技术人,求索之路道阻且艰,但一万次的翘首却比不过一次的前行。 现在,就来开启你的个人博客,发布…...
Windows下 批量重命名文件【bat实现】
目录 前言 一、Windows简单实现重命名 二、使用命令行和Excel实现重命名 前言 在实际应用中,我们经常会遇到将指定文件夹下的文件重命名,以便程序读写。 本文介绍了两种方式,都是在Windows系统中自带的重命名方式。 一、Windows简单实现…...
从 Milvus 2.2 到 2.2.6,我们是如何持续稳定升级的
最近,Milvus 发布了 2.2.6 版本,在修复了一些 bug 后,Milvus 变得越发稳定。 事实上,自 Milvus 升级至 2.X 版本以来,我们一直在努力改进及优化,推出了诸如从文件中批量导入数据、基于磁盘的近似最近邻&…...
自学python有推荐的么
大学生自学那必然是首推B站大学哇能称之为大学不是没有道理的,看看各个领域的学习分享都是非常多的,关键是看着弹幕就感觉像是在和一帮志同道合的小伙伴一起学习,自学的道路也不再孤单了,遇见不会的没准还能在弹幕和评论区找到答案…...
设计模式 --- 行为型模式
一、概述 行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。 行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在类间分…...
防御式编程
防御式编程是提高软件质量技术的有益辅助手段。就是一开始不要在代码里引入错误。使用迭代式设计、编码前写伪代码,写测试用例,助于防止引入错误。 断言 断言是用来检查永远不应该发生的非正常情况,处理这些错误的代码 错误处理技术ÿ…...
导出pdf Puppeteer 和 wkhtmltopdf区别
您可以使用第三方的 PDF 生成库来将动态页面导出为 PDF 文件。目前比较常见的是使用 Headless Chrome 或 Puppeteer 这类工具将页面转换为 PDF 文件,具体步骤如下: 安装 Headless Chrome 或 Puppeteer。 使用框架调用后端接口获取数据,渲染出…...
sequelize + Nodejs + MySQL 的简单用法
How to Use Sequelize ORM in NodeJS - Tutorial 1 Sequlize 简介 Sequelize 是最流行的可以与 Nodejs 一起使用的一种关系数据库 ORM (Object-relational mapping 对象关系映射),Mongoose 是 MongoDB 的 ORM. Sequelize 的作用,简单地说,就…...
Android Jetpack - Navigation 组件:进行应用程序导航
一. Navigation 组件的介绍 1.1 什么是 Navigation 组件 Navigation 组件是一种 Android Jetpack 库,它可以帮助开发者轻松地实现应用程序中的导航功能。导航组件包含多个类和组件,包括导航图、目的地、导航控制器等,可以帮助我们管理应用程…...
MySQL的binlog原理和它的几种使用方法
MySQL中的二进制日志(binlog)是一种用于记录数据库操作的日志文件,它可以记录MySQL服务器接收到的所有修改数据库的语句,例如INSERT、UPDATE和DELETE等语句。二进制日志对于备份和恢复数据库、复制数据库和进行数据分析等操作非常…...
40岁以上的程序员还容易找到工作吗?聊聊我自己的亲身经历
今天我们来讨论一个比较热门的话题,那就是程序员。如果到了40岁以上还容易找到工作吗?这个问题呢,其实是一个非常现实的问题,也是我们程序员非常关心的一个问题。因为我们每一个程序员,他都会有到40岁的那一天。 首先…...
Class类
package com.hspedu.reflection.class_;import com.hspedu.Cat;import java.util.ArrayList;/*** author 韩顺平* version 1.0* 对Class类特点的梳理*/ public class Class01 {public static void main(String[] args) throws ClassNotFoundException {//看看Class类图//1. Cla…...
Python小姿势 - 可选知识点:
可选知识点: 列表推导式 列表和字典推导式 字典推导式 生成器表达式 带条件的生成器表达式 解析XML 解析JSON 使用Requests和BeautifulSoup爬虫 Python并发编程 Python多线程编程 Python多进程编程 Python异步编程 Python装饰器 Python闭包 Python模块化 Python类和…...
Javaee Spring的AOP简介
一.Spring的AOP简介 1.1 什么是AOP AOP 为 Aspect Oriented Programming 的缩写,意思为面向切面编程,是通过预编译方式和运行期动态代 理实现程序功能的统一维护的一种技术。AOP 是 OOP 的延续,是软件开发中的一个热点,也是…...
基于ansible初始化linux服务器基础环境。
大家好,今天我要和大家分享一个关于搭建centos环境的新方法。 以前我们经常会看到一些文章介绍如何搭建centos环境,但很多时候都会出现一些问题。不过现在有了一种新的方法,就是使用ansible脚本来实现。 虽然这种方法仅适用于centos7&#…...
leetcode-数据库题
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 175. 组合两个表176. 第二高的薪水177. 第N高的薪水178. 分数排名181. 超过经理收入的员工182. 查找重复的电子邮箱183. 从不订购的客户 175. 组合两个表 select p…...
[元来学NVMe协议] NVMe IO 指令集(NVM 指令集)| Flush 命令
声明 主页:元存储的博客_CSDN博客 依公开知识及经验整理,如有误请留言。 个人辛苦整理,付费内容,禁止转载。 内容摘要 前言 NVMe2.0 定义的三类命令集: 管理命令集、IO命令集、Fabrics命令集 Admin Command Set (管理命令集):用于控制器的管理,如创建/销毁IO提交队列…...
信息的相关性和冗余度:信息在整个文明中的作用
文章目录 I 古埃及的象形文字1.1 罗塞塔石碑1.2 古埃及文字音节和希腊字母的对应表1.3 破解古埃及文字 I 古埃及的象形文字 1.1 罗塞塔石碑 这个石碑是在公元前196年埃及国王托勒密五世加冕一周年的诏书。 在此前大约一百年,埃及已经被来自希腊北方城邦的亚历山大…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

