第4章｜链表
Unit 01 · LeetCode #203 移除链表元素
删除节点，不是“把它藏起来”，
而是让前驱绕过它。
本单元用 dummy 节点把“删除头节点”和“删除中间节点”统一成同一个动作：检查 current.next，命中时改写前驱的 next，保留时才移动 current。
栈、队列和堆通过保留候选，等待某个事件到达后再结算答案。
链表操作不移动数组元素，而是改写 next 边。删除的本质是让入口路径绕过目标节点。
题目要求
给定链表头节点 head 和整数 val，删除链表中所有满足 Node.val == val 的节点，并返回删除后的头节点。
约束
- 节点数为
[0, 10⁴]； 1 ≤ Node.val ≤ 50；0 ≤ val ≤ 50。
示例
输出：[1,2,3,4,5]
输出：[]
输出：[]
复杂度目标
单次扫描每个节点，时间复杂度 O(n)；只使用固定数量指针，额外空间复杂度 O(1)。
放在原 head 前的虚拟节点，为原头节点提供稳定前驱，使删除头节点无需特殊分支。
要删除某节点，必须修改它的前驱节点的 next；本题 current 始终扮演前驱。
current.next = current.next.next 让前驱绕过目标节点，改变可达链。
dummy 到 current 的区域已处理完毕；current.next 是下一个尚未判断的节点。
错误 1：删除后立刻移动 current
在 [1,6,6,2] 中，第一次绕过 6 后，新的 current.next 仍然是 6。若 current 同时前移，就会跳过它。
错误：current 移到第二个 6，下一轮检查 2
错误 2：移动变量不等于删除节点
current = current.next 只改变变量指向；原前驱仍然通过 next 指向目标节点，因此结构没有变化。
current.next = current.next.next
错误 3：没有 dummy 时头节点要特判
若 head 本身等于 val，需要反复更新 head。dummy 为 head 提供稳定前驱，把所有删除统一成同一条语句。
current 始终从 dummy 开始
错误 4：返回 dummy 而不是 dummy.next
dummy 是算法辅助节点，不属于原题答案。完成后应返回真正结果入口 dummy.next。
删除排序链表中的重复元素
先阅读官方原题，再判断 #203 中哪些结构可以复用、哪些条件必须改变。不要从代码答案倒推题意。
官方题意
给定一个已按升序排列的链表 head，删除重复节点，使每个元素只出现一次，并返回仍按升序排列的链表。
输出：[1,2]
输出：[1,2,3]
- 节点数范围：
[0, 300] -100 ≤ Node.val ≤ 100- 链表保证按升序排列
① 输入 [1,1,2,3,3] 应返回什么？
② “链表已排序”提供了哪项关键保证？
任意链表 + 外部目标值 val
已排序链表，无外部目标值
current.next.val == val
current.val == current.next.val
头节点可能被全部删除，需要 dummy 稳定前驱
每组至少保留第一个节点，可直接从 head 开始
命中时执行 current.next = current.next.next
删除后不前移；保留后才前移
为什么 #83 通常不需要 dummy？
from typing import Optional
class Solution:
def deleteDuplicates(
self,
head: Optional[ListNode]
) -> Optional[ListNode]:
current = head
while current and current.next:
if current.val == current.next.val:
current.next = current.next.next
else:
current = current.next
return head
独立重写｜不自动覆盖你的答案
1. 空链表不会访问 current.next；
2. 比较 current.val 与 current.next.val；
3. 重复时绕过 current.next；
4. 不重复时 current 前移；
5. 返回 head。
Unit 01 Skill：通过前驱指针删除节点
当头节点可能被删除时，引入 dummy 获得稳定前驱。循环中只检查 current.next：命中目标就改写 current.next 并保持 current 不动；保留节点时才令 current 前移。
不会自动跳转。可以回到任意阶段复习，刷新后仍会恢复当前位置。