news 2026/4/15 0:48:39

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

作者头像

张小明

前端开发工程师

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/4/12 18:43:25

从零构建C#可靠传输协议,解决粘包、断线重连等9大难题

第一章:C#网络通信协议设计概述 在构建分布式系统和跨平台应用时,网络通信协议的设计是核心环节之一。C# 作为 .NET 平台的主要语言,提供了丰富的类库支持,如 System.Net.Sockets 和 System.IO.Pipelines,使得开发者…

作者头像 李华
网站建设 2026/3/31 12:10:21

uniapp+vuessm家庭食谱菜谱食材网上商城系统小程序ko137-vue

目录系统概述核心功能技术亮点应用场景关于博主开发技术介绍核心代码参考示例1.建立用户稀疏矩阵,用于用户相似度计算【相似度矩阵】2.计算目标用户与其他用户的相似度系统测试总结源码文档获取/同行可拿货,招校园代理 :文章底部获取博主联系方式&#x…

作者头像 李华
网站建设 2026/4/13 22:51:31

uniapp+vue微信小程序javassm图书馆座位签到离开管理系统

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

作者头像 李华
网站建设 2026/4/11 2:48:25

Three.js能否集成HeyGem输出?探索数字人视频的3D展示方式

Three.js能否集成HeyGem输出?探索数字人视频的3D展示方式 在虚拟主播频繁出没于直播间、AI客服全天候在线应答的今天,数字人早已不再是科幻电影里的专属角色。它们正以越来越自然的姿态融入我们的数字生活——但大多数时候,这些“人”还只是被…

作者头像 李华
网站建设 2026/3/23 0:34:15

【C#开发效率飞跃秘诀】:你不可错过的Lambda高级用法

第一章:Lambda表达式的核心概念与演进Lambda表达式是一种匿名函数,能够以简洁的语法将行为作为参数传递,广泛应用于函数式编程范式中。它最早出现在Lisp语言中,如今已成为Java、C#、Python、JavaScript等多种主流语言的重要特性。…

作者头像 李华
网站建设 2026/4/5 12:43:18

C#系统部署实战精要(从开发到运维的9个关键细节)

第一章:C#企业系统部署概述在现代企业级应用开发中,C#凭借其强大的生态系统和与Windows平台的深度集成,广泛应用于后端服务、桌面应用及Web系统的构建。部署C#企业系统不仅仅是将编译后的程序集发布到目标服务器,更涉及环境配置、…

作者头像 李华