链表基础与虚拟头结点 ——203. 移除链表元素
一、今日学习总结
今天正式进入链表模块的学习。链表是一种与数组截然不同的数据结构，其节点在内存中不连续，通过指针（引用）连接。
核心任务是 LeetCode 203「移除链表元素」。这道题看似简单，却完美揭示了链表操作的一个关键技巧——虚拟头结点（Dummy Node）。使用虚拟头结点可以统一处理头结点和普通节点的删除逻辑，避免繁琐的特殊判断。
二、链表基础回顾
1. 链表结构示意
text
头结点 ↓ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ │ 1 │ ●─┼──→│ 2 │ ●─┼──→│ 3 │ ●─┼──→ NULL └───┴───┘ └───┴───┘ └───┴───┘ val next val next val next
2. 数组 vs 链表对比
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分配 | 连续内存 | 非连续内存 |
| 访问方式 | 随机访问 O(1) | 顺序访问 O(n) |
| 插入/删除 | O(n)（需要移动元素） | O(1)（已知前驱节点） |
| 缓存友好性 | 高 | 低 |
3. 链表节点定义
cpp
struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };三、题目详解
题目描述：
给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回新的头节点。
示例：
text
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
四、解题思路
4.1 核心难点：头结点的特殊性
在链表中，删除普通节点只需要：
text
prev->next = curr->next;
但要删除头结点时，情况不同：
头结点没有前驱节点
删除后需要更新头指针
如果单独处理头结点，代码会变得冗长且容易出错。
4.2 解决方案：虚拟头结点
在真正的头结点前面添加一个虚拟节点，它的next指向head。
text
dummy → 1 → 2 → 6 → 3 → ... ↑ newHead (dummy->next)
优势：
原来的头结点现在有了前驱（dummy）
所有节点的删除逻辑完全统一
最后返回
dummy->next即可
4.3 算法步骤
创建虚拟头结点
dummy，其next指向head初始化
prev = dummy，curr = head遍历链表：
若
curr->val == val：删除curr（prev->next = curr->next）若不等：移动
prev = curr移动
curr = curr->next
返回
dummy->next