news 2026/2/7 6:03:25

链表专题(一):以退为进的智慧——「移除链表元素」

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
链表专题(一):以退为进的智慧——「移除链表元素」

场景想象:你是一列火车的检票员,你的任务是把所有“没买票的乘客”(值为val的节点)踢下车。

  • 如果是中间的车厢没票:很简单,让前一节车厢直接连到后一节车厢,把中间那节甩掉就行。

  • 如果是**第一节车厢(火车头)**没票:这就麻烦了。因为火车头前面没有车厢了,你没法进行“跳过”操作。你需要特殊处理,换个新车头。

痛点:为了处理“头结点可能被删除”的情况,我们通常要写两套逻辑:一套处理头结点,一套处理中间节点。这很麻烦,而且容易写错。

解决方案:虚拟头结点 (Dummy Head)我们在原来的火车头前面,硬加一节**“假车厢”**。 这样一来,原来的火车头就变成了“第二节车厢”。所有节点(包括原来的头结点)都有了“前驱节点”。 我们就不用特殊分类讨论了,一套逻辑通杀所有情况!

力扣 203. 移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/

题目分析:

  • 输入:链表的头节点head,一个整数val

  • 目标:删除链表中所有满足Node.val == val的节点。

  • 输出:新的头节点。

例子:head = [1, 2, 6, 3, 4, 5, 6], val = 6

  • 移除所有的 6。

  • 结果:[1, 2, 3, 4, 5]

核心思维:虚拟头结点 + 遍历删除

  1. 创建 Dummylet dummy = new ListNode(0, head);

    • dummy.next指向原来的head

  2. 遍历指针cur:让cur指向dummy(站在假车厢上)。

  3. 判断与删除

    • cur.next(下一节车厢)的值。

    • 如果是目标值cur.next = cur.next.next;(跳过它!注意:此时 cur 不要动,因为新接上来的车厢可能还是目标值,要继续检查)。

    • 如果不是目标值cur = cur.next;(安全,cur 往前走一步)。

  4. 返回结果:返回dummy.next(因为dummy是假的,后面挂着的才是真的新链表)。

代码实现 (JavaScript)

JavaScript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} val * @return {ListNode} */ var removeElements = function(head, val) { // 1. 创建虚拟头结点 // 它的值是多少不重要(0或者-1都行),关键是它的 next 要指向 head const dummy = new ListNode(0, head); // 2. 指针 cur 指向虚拟头结点 // 我们要通过 cur 去操作 cur.next let cur = dummy; // 3. 遍历链表 // 只要后面还有节点,就继续检查 while (cur.next !== null) { if (cur.next.val === val) { // 发现目标!执行删除操作 // 让 cur 的 next 指针跳过目标节点,直接连到下下个 cur.next = cur.next.next; // 重点细节:删除后,cur 不要往前走! // 因为新接上来的 cur.next 可能还是等于 val 的,下一轮循环要继续检查它 } else { // 不是目标,cur 安全前进一步 cur = cur.next; } } // 4. 返回真正的头结点 return dummy.next; };

深度对比:如果没有 Dummy Head 会怎样?

如果不加虚拟头结点,代码会变成这样:

JavaScript

// 【不推荐】没有 Dummy Head 的写法 var removeElements = function(head, val) { // 1. 先处理头结点连续是 val 的情况 // 比如 [6, 6, 6, 1], val=6。要把开头的 6 全删掉,head 才会变到 1 while (head !== null && head.val === val) { head = head.next; } // 2. 再处理非头结点 let cur = head; while (cur !== null && cur.next !== null) { if (cur.next.val === val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; };

你看,你需要额外写一个while循环专门去“清洗”头结点。 万一链表全是 6[6, 6, 6],删完变空了,你还得小心空指针报错。 用 Dummy Head 就可以把这两段逻辑统一,既优雅又不容易出错。

总结

这道题是链表的**“第一课”**。 请记住这个套路:凡是涉及“头结点可能会变”的操作(如删除、插入、翻转),无脑使用 Dummy Head,绝对没错。


下一题预告:反转链表

如果说这道题是热身,下一题LC 206. 反转链表就是真正的实战。

  • 题目:1 -> 2 -> 3 -> 4 -> 5

  • 变成:5 -> 4 -> 3 -> 2 -> 1

  • 这是一个需要你闭着眼睛都能写出来的算法。它是“K个一组翻转”、“回文链表”等所有高阶题目的基石。

准备好去扭转指针的方向了吗?

版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/2/6 11:22:16

前后端分离预报名管理系统系统|SpringBoot+Vue+MyBatis+MySQL完整源码+部署教程

摘要 随着教育信息化的快速发展,传统的报名管理系统在效率、扩展性和用户体验方面面临诸多挑战。学生预报名流程通常涉及大量数据交互,传统单体架构的系统难以应对高并发和动态需求。前后端分离架构因其灵活性、可维护性和高性能逐渐成为现代Web开发的主…

作者头像 李华
网站建设 2026/2/7 2:19:44

腾讯会议录制文件处理:HeyGem支持中文命名吗?

腾讯会议录制文件处理:HeyGem支持中文命名吗? 在远程办公和在线教育日益普及的今天,一场线上会议结束后,桌面上常常堆满诸如“项目复盘_王经理讲话.m4a”、“产品发布会_张总发言.mp4”这类带有中文名称的音视频文件。面对这些原…

作者头像 李华
网站建设 2026/2/6 2:21:43

uniapp+vue游乐园门票智慧向导系统小程序

目录 摘要 关于博主开发技术介绍 核心代码参考示例1.建立用户稀疏矩阵,用于用户相似度计算【相似度矩阵】2.计算目标用户与其他用户的相似度系统测试总结源码文档获取/同行可拿货,招校园代理 :文章底部获取博主联系方式! 摘要 游乐园门票智慧…

作者头像 李华
网站建设 2026/2/6 8:30:40

E4E inversion将真实人脸嵌入StyleGAN空间联动HeyGem

E4E Inversion将真实人脸嵌入StyleGAN空间联动HeyGem 在虚拟人像生成技术飞速发展的今天,一个看似简单却极具挑战的问题摆在开发者面前:如何仅凭一张照片,就让AI“变”出一个会说话、表情自然、还长得像你的数字分身?这不仅是影视…

作者头像 李华
网站建设 2026/2/6 9:12:36

[精品]基于微信小程序的社区论坛系统 UniApp

文章目录项目实现效果图所需技术栈文件解析微信开发者工具HBuilderXuniappmysql数据库与主流编程语言登录的业务流程的顺序是:毕设制作流程系统性能核心代码系统测试详细视频演示源码获取项目实现效果图 项目编号:039 所需技术栈 小程序…

作者头像 李华
网站建设 2026/2/6 11:13:19

交错数组修改总是出错?,一文读懂C#中不可忽视的核心细节

第一章:交错数组修改总是出错?根源剖析在处理复杂数据结构时,交错数组(Jagged Array)因其灵活性被广泛使用。然而,开发者在实际操作中频繁遭遇“越界访问”、“空引用”或“意外修改共享子数组”等问题。这…

作者头像 李华