算法通关村第一关——链表经典问题之删除链表元素笔记

news/2024/4/17 18:03:05

删除链表节点

总结一下高频常用的删除链表结点的情况,无论对链表进行何种操作,都需要精确查找精确指向。另外,在删除链表节点时有一个很好用的技巧:虚头结点,将头结点的特殊性转化为一般,在后面具体阐述。

删除特定节点

常用方法:直接模拟
关键:精确找到特定节点,并且将其cur.next指向cur.next.next
由于可能删除头结点,可以引入一个虚头结点dummyHead,来使得操作头结点的特殊性变得一般化,不用单独处理头结点,就和其它节点同等对待。

Code

public static ListNode removeElements(ListNode head, int val) {ListNode dummyHead = new ListNode();//虚头结点的next指向头结点headdummyHead.next = head;ListNode cur = dummyHead;while (cur.next != null) {if (cur.next.val == val) {//跳过一个节点指向,实现删除cur.next = temp.next.next;} else {cur = temp.next;}}//注意虚节点的next一定是真正的删除操作过后的链表头结点return dummyHead.next;}

删除倒数第K个节点

常用方法:双指针
关键:引入虚头结点,慢指针初始化在虚头节点,快指针初始化在原来的头节点,注意这里快节点是要走到null而不是它的下一个为null停止,因为这里快慢指针本来就有一位差距(倒也是好理解,如果都初始化在虚头节点则判定快节点的下一个为null)。
最后记得返回的是dummyHead.next

Code

 public static ListNode removeNthFromEndByTwoPoints(ListNode head, int n) {ListNode dummyHead = new ListNode(0);dummyHead.next = head;ListNode fast= head;ListNode slow = dummyHead;while (n > 0){fast = fast.next;n--;}while (fast != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyHead.next;}

删除重复元素

重复元素保留一个

常用方法:直接模拟
关键:真就直接模拟,没有任何套路,没有任何心机,就像Bob一样。

Code

public ListNode deleteDuplicates(ListNode head) {if(head == null){return head;}ListNode cur = head;while(cur.next != null){if(cur.val == cur.next.val){cur.next = cur.next.next;}else{cur = cur.next;}}return head;}

重复元素全删

常用方法:直接模拟
关键:注意引入虚头节点并从虚头结点开始寻找,比较cur.next.valcur.next.next.val是否相等,如果相等,说明这个值是重复的,将其暂存
然后再往后找,并比较后面的节点值是否还为这个重复值。遇到了就将其删去(指向跳过)。
注意,由于一下往下看了两位节点,搜索要在它们都不为空的情况下进行。

Code

public ListNode deleteDuplicates(ListNode head) {if (head == null) {return head;}ListNode dummy = new ListNode(-1111, head);ListNode cur = dummy;while (cur.next != null && cur.next.next != null) {if (cur.next.val == cur.next.next.val) {//关键在这个每一次都记录这个重复的数值int k = cur.next.val;//再消去所有val为这个重复数值的节点while (cur.next != null && cur.next.val == k) {cur.next = cur.next.next;}} else {cur = cur.next;}}return dummy.next;}

https://www.xjx100.cn/news/3118939.html

相关文章

PHP微信UI在线聊天系统源码 客服私有即时通讯系统 附安装教程

DuckChat是一套完整的私有即时通讯解决方案,包含服务器端程序和各种客户端程序(包括iOS、Android、PC等)。通过DuckChat,站点管理员可以快速在自己的服务器上建立私有的即时通讯服务,用户可以使用客户端连接至此服务器…

创建Asp.net MVC项目实现视图页面数据传值显示

MVC中视图传值 ViewData ViewBag TempData 举例创建三中传值方式实现页面数据展示 MVC中视图传值 Asp.net MVC中Controller向View传值有多种方式,这里简单说一下其中3种方式 ViewData、ViewBag和TempData ViewData ViewData存储数据,ViewData的声明和赋值方…

UI自动化测试工具工作原理是怎样的?

随着软件开发的不断演进,保障软件质量成为了至关重要的一环。在这个过程中,UI自动化测试工具崭露头角,为开发团队提供了一种强有力的方式来确保应用程序的稳定性、功能性和兼容性。本文将深入探讨UI自动化测试工具的定义、工作原理以及其在提…

从零构建属于自己的GPT系列1:文本数据预处理、文本数据tokenizer、逐行代码解读

🚩🚩🚩Hugging Face 实战系列 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在PyCharm中进行 本篇文章配套的代码资源已经上传 从零构建属于自己的GPT系列1:文本数据预处理 从零构建属于自己的GPT系列2:语…

企业微信http协议接口开发,发送位置消息

产品说明 一、 hook版本:企业微信hook接口是指将企业微信的功能封装成dll,并提供简易的接口给程序调用。通过hook技术,可以在不修改企业微信客户端源代码的情况下,实现对企业微信客户端的功能进行扩展和定制化。企业微信hook接口…

Echarts大屏-数据可视化

使用原生htmljavascript实现大屏展示,较为麻烦的为边框的四个小角使用伪元素生成,其余echarts使用如下快速上手 - Handbook - Apache ECharts 效果如下:

springMVC日志

简单介绍 Logback是完全实现SLF4J接口API(也叫日志门面)的日志框架。 Logback 的架构非常通用,可以应用于不同的环境。目前logback分为三个模块,logback-core、logback-classic和logback-access。 logback-core 模块为其他两个模块奠定了基础。logbac…

【Springboot系列】SpringBoot整合Jpa

文章目录 前言:什么是JPA?JPA优缺点优点1.简化开发:2.高度抽象:3.跨数据库支持:4.自动化的事务管理: 缺点1.学习成本较高:2.性能问题:3.灵活性受限: 示例版本依赖代码Use…