当前位置: 首页 > 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;形成“端云大数据”的业务体系和新的管理…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;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模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

有限自动机到正规文法转换器v1.0

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