【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 的后继就不会在更新了

在这里插入图片描述

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

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

相关文章

基于QTreeWidget实现带Checkbox的多级组织结构选择树

基于QTreeWidget实现带Checkbox的多级组织结构选择树 采用基于QWidgetMingw实现的原生的组织结构树 通过QTreeWidget控件实现的带Checkbox多级组织结构树。 Qt相关系列文章: 一、Qt实现的聊天画面消息气泡 二、基于QTreeWidget实现多级组织结构 三、基于QTreeWidget…

eclipse连接mysql数据库(下载eclipse,下载安装mysql,下载mysql驱动)

前言: 使用版本:eclipse2017,mysql5.7.0,MySQL的jar建议使用最新的,可以避免警告! 1:下载安装:eclipse,mysql在我之前博客中有 http://t.csdnimg.cn/UW5fshttp://t.csdn…

2023年最详细的:本地Linux服务器安装宝塔面板,并内网穿透实现公网远程登录

📚📚 🏅我是默,一个在CSDN分享笔记的博主。📚📚 ​​ 🌟在这里,我要推荐给大家我的专栏《Linux》。🎯🎯 🚀无论你是编程小白,还是有一…

插头是什么

插头 电工电气百科 文章目录 插头前言一、插头是什么二、插头的类别三、插头的作用原理总结前言 插头的设计和结构会根据不同的国家和地区的标准和电源类型而有所不同。所以,在使用插头时,需要注意使用符合当地标准和规定的插头,以确保电气安全以及插入正确的电源插座 一、…

【lombok】从easyExcel read不到值到cglib @Accessors(chain = true)隐藏的大坑

背景: 在一次使用easyExcel.read 读取excel时,发现实体类字段没有值,在反复测试后,发现去掉Accessors(chain true)就正常了,为了验证原因,进行了一次代码跟踪 由于调用链路特别长,只列举出部分代码&#x…

动态规划习题

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

LCR 120. 寻找文件副本

解题思路&#xff1a; 利用增强for循环遍历documents&#xff0c;将遇见的id加入hmap中&#xff0c;如果id在hamp中存在&#xff0c;则直接返回id class Solution {public int findRepeatDocument(int[] documents) {Set<Integer> hmapnew HashSet<>();for(int d…

Python+Selenium UI自动化测试环境搭建及使用

一、什么是Selenium &#xff1f; Selenium 是一个浏览器自动化测试框架&#xff0c;它主要用于web应用程序的自动化测试&#xff0c;其主要特点如下&#xff1a;开源、免费&#xff1b;多平台、浏览器、多语言支持&#xff1b;对web页面有良好的支持&#xff1b;API简单灵活易…

【C++11特性篇】盘点C++11中三种简化声明的方式【auto】【decltype】【nullptr】(3)

前言 大家好吖&#xff0c;欢迎来到 YY 滴C系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; 目录 一.auto&#xff06;范围for二.decltyp…

Java医院3D人体智能导诊系统源码 Uniapp+springboot 微信小程序

“智能导诊”以人工智能手段为依托&#xff0c;为人们提供智能分诊、问病信息等服务&#xff0c;在一定程度上满足了人们自我健康管理、精准挂号等需求。智能导诊可根据描述的部位和病症&#xff0c;给出适合病症的科室参考。 智能导诊页面会显示男性或女性的身体结构图&#x…

Linux基本操作指令

哈喽小伙伴们&#xff0c;从这篇文章开始&#xff0c;在学习数据结构的同时&#xff0c;我们开启一个新的篇章——Linux操作系统的学习&#xff0c;这将会是又一个新的开始&#xff0c;希望小伙伴们能够认真细心&#xff0c;不要掉队哦。 目录 一.什么是Linux 二.为什么要学习…

LeetCode 300最长递增子序列 674最长连续递增序列 718最长重复子数组 | 代码随想录25期训练营day52

动态规划算法10 LeetCode 300 最长递增子序列 2023.12.15 题目链接代码随想录讲解[链接] int lengthOfLIS(vector<int>& nums) {//创建变量result存储最终答案,设默认值为1int result 1;//1确定dp数组&#xff0c;dp[i]表示以nums[i]为结尾的子数组的最长长度ve…

JNA实现JAVA调用C/C++动态库

1.JNA JNA全称Java Native Access&#xff0c;是一个建立在经典的JNI技术之上的Java开源框架&#xff08;https://github.com/twall/jna&#xff09;。JNA提供一组Java工具类用于在运行期动态访问系统本地库&#xff08;native library&#xff1a;如Window的dll&#xff09;而…

CSS学习笔记整理

CSS 即 层叠样式表/CSS样式表/级联样式表&#xff0c;也是标记语言&#xff0c; 用于设置HTML页面中的文本内容&#xff08;字体、大小、对齐方式等&#xff09;、图片的外形&#xff08;宽高、边框样式、边距&#xff09;以及版面的布局和外观显示样式 目录 准备工作 Chrome调…

时间序列预测 — CNN-LSTM实现多变量多步光伏预测(Tensorflow)

目录 1 数据处理 1.1 导入库文件 1.2 导入数据集 1.3 缺失值分析 2 构造训练数据 ​3 模型训练 3.1 CNN-LSTM网络 3.2 模型训练 4 模型预测 专栏链接&#xff1a;https://blog.csdn.net/qq_41921826/category_12495091.html 1 数据处理 1.1 导入库文件 import scip…

『番外篇二』Swift “黑魔法”之动态获取类实例隐藏属性的值

概览 在 Swift 代码的调试中,我们时常惊叹调试器的无所不能:对于大部分“黑盒”类实例的内容,调试器也都能探查的一清二楚。 想要自己在运行时也能轻松找到 Thread 实例“私有”属性的值吗(比如 seqNum)? 在本篇博文中您将学到如下内容: 概览1. 借我,借我,一双慧眼吧…

深入理解LightGBM

1. LightGBM简介 GBDT (Gradient Boosting Decision Tree) 是机器学习中一个长盛不衰的模型&#xff0c;其主要思想是利用弱分类器&#xff08;决策树&#xff09;迭代训练以得到最优模型&#xff0c;该模型具有训练效果好、不易过拟合等优点。GBDT不仅在工业界应用广泛&#…

IT 人员与加密程序:如何战胜病毒

&#x1f510; 加密程序是攻击者在成功攻击组织时使用最多的恶意软件类型。它们通常会发送到一个庞大的电子邮件地址数据库&#xff0c;看起来像 Word 或 Excel 文档或 PDF 文件。 想象一下&#xff0c;你是会计部门的一名员工。这种格式的文件在电子文档管理系统中被广泛使用…

如何查看Linux中glibc的Version

用ldd --version ldd --version 运行libc.so 你没有看错&#xff0c;libc.so是一个可执行程序。 但前提是你要找到它。因为它并不在PATH所包含的目录下。 ppdell:~$ ldd which cat | grep libclibc.so.6 > /lib/x86_64-linux-gnu/libc.so.6 (0x00007f0e6fb34000)ppdell:~…

dcoker-compose一键部署EFAK —— 筑梦之路

简介 EFAK&#xff08;Eagle For Apache Kafka&#xff0c;以前称为 Kafka Eagle&#xff09;是一款由国内公司开源的Kafka集群监控系统&#xff0c;可以用来监视kafka集群的broker状态、Topic信息、IO、内存、consumer线程、偏移量等信息&#xff0c;并进行可视化图表展示。独…