LeetCode 剑指 Offer 18. 删除链表的节点
题目描述
题意分析
本文题面包含三种口径，需要先分清输入与删除要求。链接中的力扣题给出头节点
head和目标值val，保证节点值互不相同，删除对应节点并返回新头；下面第一种解法处理这一版本。删除所有值等于
val的节点属于扩展写法，允许连续匹配，需要继续扫描整条链表。上方书题图片则直接给出待删节点指针，讨论能否省去查找前驱的遍历，不能把“已知节点”与“只知道节点值”混为一谈。单链表没有前驱指针，普通删除需要让前一个节点跳过目标。删除头节点时结果入口会改变，因此无论采用哪一种版本，都要正确返回修改后的头节点。
解法：哑节点统一删除位置
核心思路
[!blue]
在原头节点前增加一个哑节点
dummy，令pre指向待检查节点的前驱，真正检查的是pre.next。这样原头节点也拥有可修改的前驱，删除头部与删除中间节点可以使用同一条连接操作。只要后继存在且值不是目标，就让
pre前进一步。循环结束有两种情况：后继为空，说明没有找到目标，保持链表不变；后继值等于val，说明前驱已经定位，执行pre.next = pre.next.next即可绕过目标节点。力扣版本保证节点值互不相同，因此找到一个目标后就完成了删除，不必继续扫描。这个实现若用于含重复值的普通链表，只会删除第一个匹配节点；删除全部匹配值需要后面的第二种写法。
最后返回
dummy.next。头节点被删时，它已经指向新的头；唯一节点被删时它变为空；其他位置被删时，原头仍然保留。哑节点的占位值不参与比较。
解题步骤
- 创建指向原头的
dummy，令pre = dummy。- 当后继存在且值不等于目标时，继续移动前驱。
- 若找到匹配后继，令前驱直接指向它的下一个节点。
- 返回
dummy.next，没有找到目标时原链表保持不变。
代码实现
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
// pre 永远指向待检查节点的前驱，删除头节点和中间节点逻辑一致。
while (pre.next != null && pre.next.val != val) {
pre = pre.next;
}
if (pre.next != null) {
// 修改前驱连接，真正跳过待删节点。
pre.next = pre.next.next;
}
// 删除首节点时入口会改变，从虚拟头取结果。
return dummy.next;
}
}
func deleteNode(head *ListNode, val int) *ListNode {
dummy := &ListNode{Next: head}
pre := dummy
// pre 永远指向待检查节点的前驱，删除头节点和中间节点逻辑一致。
for pre.Next != nil && pre.Next.Val != val {
pre = pre.Next
}
if pre.Next != nil {
// 修改前驱连接，真正跳过待删节点。
pre.Next = pre.Next.Next
}
// 删除首节点时入口会改变，从虚拟头取结果。
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 单链表删除需要操作目标的前驱连接。
- 结果入口可能改变，所以从虚拟头重新取头。
解法二：按值删除全部匹配节点
核心思路
[!blue]
第一张图片要求删除全部匹配值，因此前驱不能在第一次删除后结束查找。仍然检查
pre.next：匹配就跳过它，保持pre不动；不匹配才让pre移到这个已确认保留的节点。删除后不移动前驱，是因为新接过来的后继还未检查，也可能等于目标。只有确定后继应保留时，才把它纳入处理好的前缀。这样每个真实节点都会被检查一次，连续目标、多个分散目标以及全部删除都能统一处理。
解题步骤
- 创建虚拟头并令前驱从它开始。
- 后继匹配目标时修改连接跳过它，前驱保持不动。
- 后继不匹配时，将前驱向后移动一格。
- 重复到后继为空，返回虚拟头后面的节点。
代码实现
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null) {
if (pre.next.val == val) {
pre.next = pre.next.next;
} else {
pre = pre.next;
}
}
return dummy.next;
}
}
func deleteNode(head *ListNode, val int) *ListNode {
dummy := &ListNode{Next: head}
pre := dummy
for pre.Next != nil {
if pre.Next.Val == val {
pre.Next = pre.Next.Next
} else {
pre = pre.Next
}
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点恰好作为后继检查一次。
- 空间复杂度：$O(1)$，只使用虚拟头和前驱指针。
关键点总结
[!green]
- 删除后继续检查新后继：不推进前驱才能覆盖连续的匹配节点。
- 结果入口统一读取：始终返回
dummy.next，不会把已经删除的原头重新返回。
解法三：已知待删节点指针
核心思路
[!blue]
书题直接提供待删节点
node，并假定它属于给定链表。若它不是尾节点，可以把后继节点的值复制到当前节点，再让当前节点跳过后继。结果中的值序列等价于删除当前逻辑位置，但实际被移出链表的对象是后继节点，当前对象保存后继的值继续存在。这种操作只访问当前节点和后继，不需要前驱，所以非尾节点可以在常数时间内处理。若目标是尾节点，就没有后继可复制，仍要从头找到它的前驱，再把前驱的
next设为空；单节点链表直接返回空即可。因此不能把书图中的常数时间要求理解成所有位置的最坏情况都能达到。只有头指针和待删节点指针时，非尾节点可用复制后继的办法省掉遍历，删除多节点链表的尾节点仍然需要线性查找。
解题步骤
- 头节点或待删节点为空时，返回原头。
- 待删节点有后继时，复制后继值并跳过后继，返回原头。
- 没有后继且目标就是头节点时，整条链只有一个节点，返回空。
- 否则从头定位尾节点的前驱，将其后继设为空，再返回原头。
代码实现
class Solution {
public ListNode deleteNode(ListNode head, ListNode node) {
if (head == null || node == null) {
return head;
}
if (node.next != null) {
node.val = node.next.val;
node.next = node.next.next;
return head;
}
if (head == node) {
return null;
}
ListNode pre = head;
while (pre.next != node) {
pre = pre.next;
}
pre.next = null;
return head;
}
}
func deleteNode(head *ListNode, node *ListNode) *ListNode {
if head == nil || node == nil {
return head
}
if node.Next != nil {
node.Val = node.Next.Val
node.Next = node.Next.Next
return head
}
if head == node {
return nil
}
pre := head
for pre.Next != node {
pre = pre.Next
}
pre.Next = nil
return head
}
复杂度分析
- 时间复杂度：非尾节点和单节点链表为 $O(1)$；删除多节点链表的尾节点为 $O(n)$，所以最坏为 $O(n)$。
- 空间复杂度：$O(1)$，只使用固定数量的节点引用。
关键点总结
[!green]
- 输入是节点引用：不再按值寻找目标；前提是非空目标确实属于这条链表。
- 复制后继改变的是逻辑位置：目标对象继续存在，移除的是它的后继对象。
- 尾节点不能套用复制法：没有后继时需要找到前驱，复杂度与非尾情况不同。
易错点总结
[!yellow]
- 只移动局部变量到下一个节点，不会改变链表连接。
- 删除首节点后仍返回旧头，会返回被删除的节点。
- 查找时不检查 next 是否为空，可能访问空节点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 27. 移除元素 | 简单 | 同样删除指定值，数组用覆盖压缩，链表通过前驱next跳过节点。 |
| 82. 删除排序链表中的重复元素 II | 中等 | 同样用哑节点处理可能被删的头段，原题先判断重复值段，本题按固定值筛选。 |