当前位置: 首页 > news >正文

【leetcode】链表总结

说明:本文内容来自于代码随想录

image.png

链表基本操作

https://leetcode.cn/problems/design-linked-list/

删除节点

https://leetcode.cn/problems/remove-linked-list-elements/description/,删除节点,虚拟头节点。定义两个节点,分别为前继节点 pre 和当前节点 cur。当前节点初始化为头节点。每次判断当前节点是否需要删除。若要删除,则将前继节点的下一个指向当前节点的下一个;否则,更新前继节点为当前节点。最后当前节点移动到下一个节点。
要点:

  1. 头节点的删除和其他节点的删除是不一样的。因为删除是将被删除节点的前继节点指向被删除节点的后继,但是头节点没有前继。所以需要定义一个虚拟头节点,其后继指向 head
  2. 删除后,新的头节点为虚拟头节点的后继

代码如下:

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;
}

反转链表

思路:

  1. 用两个指针分别指向前一个 pre 和当前节点 cur,当前节点初始化为头节点 pre=head
  2. 每次操作,头节点指向前一个,cur.next = pre,然后 pre 和 cur 分别前进一个单位
  3. 由于改变了 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/
image.png
交换涉及到 3 步,所以需要 3 个指针 pre, cur, next,分别表示上一个的前继、上一个、下一个(注意图中的 cur 指的是这里的 pre,图里的 1 是这里的 cur,图里的 2 是这里的 next):

  1. 上一个的后继指向下一个的后继,cur.next = next.next
  2. 下一个的后继指向上一个,next.next = cur
  3. 上一个的前继的后继指向下一个,pre.next = next
// 交换
cur.next = next.next;
next.next = cur;
pre.next = next;

注意需要更新头节点,即:当第一次交换完之后,更新头节点为 next

删除链表倒数第 n 个节点

链表相交

环形链表

总结

image.png
哑节点(dummy node)在链表中很常用,比如:

  • 删除节点,涉及到 2 个节点,当前节点 cur 和当前节点的前继 pre。如果删除的是头节点,就没有前继,所以需要哑节点
  • 交换节点,涉及到 3 个节点,当前节点 cur、当前节点的前继 pre、当前节点的后继 next。类似的,头节点没有前继,所以需要哑节点

说明:由于这些操作有可能会修改头节点,所以在操作的时候,除了哑节点 dummy,还要定义 pre 节点:

  1. 初始化,pre = dummy
  2. 后续的操作中,只移动 pre,dummy 保持不变
  3. 由于第一次 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亿&#xff0…...

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>标签 文本修饰符 字体为斜体的修饰&#xff0c;一对星号包含 字符为粗体&#xff0c;两对星号包含 字体为…...

UE5 动画 Sequencer-学习笔记

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

visual studio code 好用的插件

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

Redis 过期删除策略、内存回收策略、单线程理解

不知从何开始Redis的内存淘汰策略也开始被人问及&#xff0c;卷&#xff01;真的是太卷了。难不成要我们去阅读Redis源码吗&#xff0c;其实问题的答案&#xff0c;在Redis中的配置文件中全有&#xff0c;不需要你阅读源码、这个东西就是个老八股&#xff0c;估计问这个东西是想…...

oracle 如何把数据库 date 日期格式 的数据 改成 2021-01-27

如果您要将日期"27-12月-29"更改为"2021-01-27"格式&#xff0c;您可以使用Oracle的日期格式化函数和字符串替换函数来实现。 以下是一个示例SQL语句&#xff0c;将日期"27-12月-29"更改为"2021-01-27"格式&#xff1a; sql UPDATE…...

Git 使用教程(超级详细)

目录 一&#xff1a;Git二&#xff1a;SVN与Git的的区别三、安装Git四&#xff1a;常规操作五&#xff1a;远程仓库六&#xff1a;创建与合并分支七&#xff1a;bug分支八&#xff1a;多人协作九&#xff1a;git可视化工具 Git Git 是一种分布式版本控制系统&#xff0c;用于…...

动态规划习题

动态规划的核心思想是利用子问题的解来构建整个问题的解。为此&#xff0c;我们通常使用一个表格或数组来存储子问题的解&#xff0c;以便在需要时进行查找和使用。 1.最大字段和 #include <iostream> using namespace std; #define M 200000int main() {int n, a[M], d…...

安卓免Root做klipper上位机教程

软件说明&#xff1a;虚拟电脑可以在8.0以上没越狱的安卓系统中安装klipper上位机程序实现对已刷入klipper固件的3D打印控制板的控制欢迎下载安装测试&#xff0c;反馈碰到的问题。安装步骤&#xff1a;1). 在手机上打开浏览器&#xff0c;访问这个网址 http://droidvm.com/cn/…...

网络安全学习之信息泄露

一、背景以及泄露途径 通常我们会对数据进行备份&#xff0c;比如我们在发布网站的时候会对将要替换的版本进行备份。我们在对重要文件进行修改的时候我们也需要进行备份&#xff0c;如果我们对备份或缓存的文件或信息为做好管理&#xff0c;很容易就导致我们的敏感信息泄露。…...

Java智慧工地源码,智慧工地管理平台的技术架构和工作原理

智慧工地管理平台是将互联网的理念和技术引入建筑工地&#xff0c;从施工现场源头抓起&#xff0c;最大程度的收集人员、安全、环境、材料等关键业务数据&#xff0c;依托物联网、互联网&#xff0c;建立云端大数据管理平台&#xff0c;形成“端云大数据”的业务体系和新的管理…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

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

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

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...