【leetcode】链表总结
说明:本文内容来自于代码随想录
链表基本操作
https://leetcode.cn/problems/design-linked-list/
删除节点
https://leetcode.cn/problems/remove-linked-list-elements/description/,删除节点,虚拟头节点。定义两个节点,分别为前继节点 pre 和当前节点 cur。当前节点初始化为头节点。每次判断当前节点是否需要删除。若要删除,则将前继节点的下一个指向当前节点的下一个;否则,更新前继节点为当前节点。最后当前节点移动到下一个节点。
要点:
- 头节点的删除和其他节点的删除是不一样的。因为删除是将被删除节点的前继节点指向被删除节点的后继,但是头节点没有前继。所以需要定义一个虚拟头节点,其后继指向 head
- 删除后,新的头节点为虚拟头节点的后继
代码如下:
public ListNode removeElements(ListNode head, int val) {// 前继节点的下一个指向当前节点// 若当前节点需要删除,则将前继节点的下一个指向当前节点的下一个ListNode dummy = new ListNode(-1, head); // 虚拟节点,指向头节点ListNode pre = dummy;ListNode cur = head;while (cur != null) {if (cur.val == val) { // 当前节点需要删除pre.next = cur.next;} else { // 当前节点不需要删除,则更新前继节点为当前节点pre = cur; }cur = cur.next; // 当前节点往前移动一位}// 最开始,pre.next和dummy指向的实际上是同一个地址。当pre.next发生变化时,dummy.next也发生变化// 但是pre和dummy不是同一个地址。所以当修改pre = cur时,dummy是不变的。// 所以最开始如果pre.next发生了更新的话,那么dummy.next也会同步更新,即更新的是头节点。// 一旦pre发生了更新,则下一次的pre.next更新就不会影响头节点了,影响的是头节点后面的节点。return dummy.next;
}
在头部插入节点
public ListNode insertHead(ListNode head, int val) {ListNode newNode = new ListNode(val);newNode.next = head; // 新节点的后继指向旧头节点head = newNode; // 更新头节点为新节点return head;
}
反转链表
思路:
- 用两个指针分别指向前一个 pre 和当前节点 cur,当前节点初始化为头节点 pre=head
- 每次操作,头节点指向前一个,cur.next = pre,然后 pre 和 cur 分别前进一个单位
- 由于改变了 cur 的下一个之后,前进的时候就无法找到原来的下一个了,所以需要在操作之前暂存下一个 next = cur.next
动画:
https://code-thinking.cdn.bcebos.com/gifs/206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.gif
迭代版
public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {// 保存cur的下一个节点ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;
}
递归版
public ListNode reverse(ListNode pre, ListNode cur) {if (cur == null) return pre;// 反转ListNode next = cur.next;cur.next = pre;return reverse(cur, next);
}public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;return reverse(pre, cur);
}
交换成对节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/
交换涉及到 3 步,所以需要 3 个指针 pre, cur, next
,分别表示上一个的前继、上一个、下一个(注意图中的 cur 指的是这里的 pre,图里的 1 是这里的 cur,图里的 2 是这里的 next):
- 上一个的后继指向下一个的后继,cur.next = next.next
- 下一个的后继指向上一个,next.next = cur
- 上一个的前继的后继指向下一个,pre.next = next
// 交换
cur.next = next.next;
next.next = cur;
pre.next = next;
注意需要更新头节点,即:当第一次交换完之后,更新头节点为 next
删除链表倒数第 n 个节点
链表相交
环形链表
总结
哑节点(dummy node)在链表中很常用,比如:
- 删除节点,涉及到 2 个节点,当前节点 cur 和当前节点的前继 pre。如果删除的是头节点,就没有前继,所以需要哑节点
- 交换节点,涉及到 3 个节点,当前节点 cur、当前节点的前继 pre、当前节点的后继 next。类似的,头节点没有前继,所以需要哑节点
说明:由于这些操作有可能会修改头节点,所以在操作的时候,除了哑节点 dummy,还要定义 pre 节点:
- 初始化,pre = dummy
- 后续的操作中,只移动 pre,dummy 保持不变
- 由于第一次 pre 和 dummy 的后继指向的是同一个,所以 pre 的后继更新了,dummy 的后继也会更新,即达到了更新头节点的目的。后续移动 pre 之后,pre 的后继和 dummy 的后继就不是同一个了, dummy 的后继就不会在更新了
相关文章:

【leetcode】链表总结
说明:本文内容来自于代码随想录 链表基本操作 https://leetcode.cn/problems/design-linked-list/ 删除节点 https://leetcode.cn/problems/remove-linked-list-elements/description/,删除节点,虚拟头节点。定义两个节点,分别…...
焦虑,其实是你自愿选择的
如果一个人想要焦虑,他可以永远焦虑下去 从上学,到找工作,从买房到结婚生娃,他总是可以选择用自己的头脑去过度思考未来还没有发生的事情,从而让自己无限焦虑下去,直到生命终结。 我们的生命是存在于当下…...

4G无线工业级路由器在智能制造设备互联互通中的角色
随着工业技术的不断发展和进步,智能制造已经成为了现代制造业的重要趋势和发展方向。而在智能制造过程中,设备之间的互联互通是至关重要的一环。在这个过程中,4G无线工业级路由器扮演着重要的角色,它提供了稳定可靠的网络连接&…...

gitbash下载安装
参考教程 零、下载 官网地址 2.43.0win64 链接:https://pan.baidu.com/s/16urs_nmky7j20-qNzUTTkg 提取码:7jaq 一、安装 图标组件(Additional icons):选择是否创建桌面快捷方式;桌面浏览(Win…...

系列一、Linux中安装MySQL
一、Linux中安装MySQL 1.1、下载MySQL安装包 官网:https://dev.mysql.com/downloads/file/?id523327 我分享的: 链接:https://pan.baidu.com/s/188_9RnBYlWVzFb_UJH5aaQ?pwdyyds 提取码:yyds 1.2、上传至/opt目录 & 解压…...

开辟“护眼绿洲”,荣耀何以为师?
文 | 智能相对论 作者 | 佘凯文 俗话说,眼睛是心灵的窗户,可如今,人们对于这扇“窗户”的保护,似乎越来越不重视。 据人民日报今年发布的调查显示,中国眼病患病人数2.1亿,近视患者人数多达6亿࿰…...
Modbus RTU和Modbus TCP的区别 深入篇
目录 1 传输方式不同 2 硬件接口不同 3 校验码不同 4 指令内容不同 4.1 Modbus RTU 4.1.1 功能码为03,表示读寄存器 4.1.2 功能码为10,表示写多个寄存器 4.2 Modbus TCP 4.2.1 功能码为03,表示读寄存器 4.2.2 回复异常报文 5 传输速…...
【大数据】Doris 的集群规划和环境准备
Doris 的集群规划和环境准备 1.1 环境要求1.1 Linux 操作系统版本需求1.2 软件需求 1.2 硬件要求1.3 节点规划1.4 通信端口1.5 IP 地址绑定 Doris 作为一款开源的 MPP 架构 OLAP 数据库,能够运行在绝大多数主流的商用服务器上。为了能够充分运用 MPP 架构的并发优势…...

connect: Network is unreachable问题解决
第一步:查看ifcfg-ens33配置文件 cd /etc/sysconfig/network-scripts/ cat ifcfg-ens33 发现问题:GATEWAY写错成GATWAY 第二步:修改 vim ifcfg-ens33 第三步:检测是否成功 ping baidu.com 成功!...

三层交换与DHCP
目录 一、三层交换 (一)基本概念 (二)转发原理 (三)ensp项目实验 二、DHCP (一)DHCP工作原理 1.DHCP的特点 2.工作原理 (二)DHCP项目实验 一、三层交…...

02markdown-学习笔记
一级标题 二级标题 三级标题 四级标题 五级标题 六级标题 换行符<br>标签 写入一段测试用的正文第二段测试文本,如果要对文本进行换行可以使用<br>标签 文本修饰符 字体为斜体的修饰,一对星号包含 字符为粗体,两对星号包含 字体为…...

UE5 动画 Sequencer-学习笔记
P2. 课程介绍 资料:https://www.bilibili.com/video/BV1Ag411873f?p2&vd_source707ec8983cc32e6e065d5496a7f79ee6 Sequencer不仅可以做互动动画,还可以导出视频与序列帧 P3-4. 界面介绍 https://www.bilibili.com/video/BV1Ag411873f?p3&spm_…...

visual studio code 好用的插件
vscode-icons Better comments 该插件对不同类型的注释会附加了不同的颜色,更加方便区分,帮助我们在代码中创建更人性化的注释。 Error Lens Error Lens插件是一款可以检测你编写的代码的语法错误,并且会显示出对语法错误的诊断信息…...

Redis 过期删除策略、内存回收策略、单线程理解
不知从何开始Redis的内存淘汰策略也开始被人问及,卷!真的是太卷了。难不成要我们去阅读Redis源码吗,其实问题的答案,在Redis中的配置文件中全有,不需要你阅读源码、这个东西就是个老八股,估计问这个东西是想…...
oracle 如何把数据库 date 日期格式 的数据 改成 2021-01-27
如果您要将日期"27-12月-29"更改为"2021-01-27"格式,您可以使用Oracle的日期格式化函数和字符串替换函数来实现。 以下是一个示例SQL语句,将日期"27-12月-29"更改为"2021-01-27"格式: sql UPDATE…...

Git 使用教程(超级详细)
目录 一:Git二:SVN与Git的的区别三、安装Git四:常规操作五:远程仓库六:创建与合并分支七:bug分支八:多人协作九:git可视化工具 Git Git 是一种分布式版本控制系统,用于…...

动态规划习题
动态规划的核心思想是利用子问题的解来构建整个问题的解。为此,我们通常使用一个表格或数组来存储子问题的解,以便在需要时进行查找和使用。 1.最大字段和 #include <iostream> using namespace std; #define M 200000int main() {int n, a[M], d…...
安卓免Root做klipper上位机教程
软件说明:虚拟电脑可以在8.0以上没越狱的安卓系统中安装klipper上位机程序实现对已刷入klipper固件的3D打印控制板的控制欢迎下载安装测试,反馈碰到的问题。安装步骤:1). 在手机上打开浏览器,访问这个网址 http://droidvm.com/cn/…...
网络安全学习之信息泄露
一、背景以及泄露途径 通常我们会对数据进行备份,比如我们在发布网站的时候会对将要替换的版本进行备份。我们在对重要文件进行修改的时候我们也需要进行备份,如果我们对备份或缓存的文件或信息为做好管理,很容易就导致我们的敏感信息泄露。…...

Java智慧工地源码,智慧工地管理平台的技术架构和工作原理
智慧工地管理平台是将互联网的理念和技术引入建筑工地,从施工现场源头抓起,最大程度的收集人员、安全、环境、材料等关键业务数据,依托物联网、互联网,建立云端大数据管理平台,形成“端云大数据”的业务体系和新的管理…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...