LeetCode 面试题 02.03. 删除中间节点
目录
题目描述
题意分析
这道题最反直觉的地方在于函数签名：只给一个待删节点
node，既没有 head，也没有返回值。这意味着无法从头遍历找前驱，也无法通过返回新头节点来表达结果——所有修改必须原地作用在传入的这条链表上，调用方从外部的 head 看过去必须已经生效。常规删除靠的是「让前驱的 next 跳过自己」，而单链表节点没有指向前驱的指针，在只拿到 node 的情况下前驱是不可达的。所以题目实际上禁掉了标准删除路径，逼你换一个角度理解「删除」。
约束「待删除节点一定不是尾节点」是整道题的题眼。它保证了
node.next必然存在，从而后继节点可以被安全访问。同时它也是这个解法的适用边界：如果允许删尾节点，任何只拿到 node 的方法都无解，因为前驱的 next 必须被改成 null，而前驱不可达。还要注意题目对「删除」的验收标准是链表的值序列，而不是节点对象的内存地址。只要从 head 遍历得到的值序列里少了 node 原本的值、其余顺序不变，就算删对了，没人会检查哪个内存块被回收。这一点直接打开了下面的解法空间。
边界上：由于保证非尾节点，链表长度至少为 2，node 至少有一个后继；node 是否为头节点不影响做法，因为整个操作根本不碰前驱。
解法：复制后继节点并跳过
核心思路
常规删除需要前驱执行
prev.next = node.next，但题目只给待删节点，没有头节点，无法找到前驱。关键条件是node不是尾节点，因此它一定有后继。不必真的移除
node这个对象：先把后继节点的值复制到node，再让node.next跳过后继。对从链表头遍历的调用者而言，原来位于node的值消失了，后面的值仍保持原顺序，效果与删除指定节点一致。状态定义：把局部值序列写成
... → v(node) → w(next) → rest。第一步后变为... → w(node) → w(next) → rest，第二步后变为... → w(node) → rest。正确性说明：操作前缀完全不变；
node改为承载后继值w，再摘除原后继，因此结果只少了原值v；rest的连接和顺序均未改变。所以最终值序列恰好等于删除node后的序列。该方法依赖“非尾节点”和题目只关心链表值序列这两个前提。
解题步骤
- 读取
node.next.val，覆盖node.val，使原待删值消失。- 将
node.next改为node.next.next，摘除产生的重复后继节点。例如
[4,5,1,9]删除值为 5 的节点：复制后局部序列为[4,1,1,9]，跳过后继后得到[4,1,9]。两行顺序不能交换，因为改完next后就无法再读取被跳过节点的值。若待删节点是尾节点，则仅凭当前节点无法修改其前驱，问题无解；题目已明确排除该情况。
代码实现
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
func deleteNode(node *ListNode) {
node.Val = node.Next.Val
node.Next = node.Next.Next
}
复杂度分析
- 时间复杂度：
O(1)。只进行两次局部赋值。- 空间复杂度：
O(1)。不创建新节点或辅助容器。
关键点总结
- 函数签名没有 head，说明常规“找前驱再删除”路径不可用。
- 复制后继值并摘除后继，在题目的值序列语义下等价于删除当前节点。
- “待删节点不是尾节点”是解法成立的必要条件，不是可忽略的边界说明。
- 修改链表结构前先读取仍需使用的信息：先复制值，再改
next。
易错点总结
- 两行顺序写反：
[4,5,1,9]删除 5 时，先跳过节点 1 再复制会得到[4,9,9]；若链表是[1,2]，还会空指针异常。- 只复制值、不跳过后继：
[4,5,1,9]会变成[4,1,1,9]，节点数没有减少。- 只修改
next、不复制值：同一用例会变成[4,5,9]，实际删掉的是后继值 1。- 写成
node = node.next：这只改变函数内局部变量，前驱仍指向原节点，外部链表完全不变。- 试图给尾节点执行同样操作：
node.next为null/nil，必然崩溃；没有 head 或前驱时无法删除尾节点。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 237. 删除链表中的节点 | 中等 | 与本题完全同构的另一编号版本，可用来验证同一套两行写法在不同签名下的迁移 |
| 203. 移除链表元素 | 简单 | 给了 head 且要按值批量删除，头节点可能被删，需要哑结点统一前驱 |
| 83. 删除排序链表中的重复元素 | 简单 | 有序数组上删重复只保留一个，靠单指针比较相邻值，不需要哑结点 |
| 82. 删除排序链表中的重复元素 II | 中等 | 重复值要全部删光，必须用前驱指针加内层跳跃循环，边界比 83 复杂一层 |
| 面试题 02.01. 移除重复节点 | 简单 | 链表无序，需要哈希集合记录已出现的值，考察空间换时间与不用额外空间的取舍 |
| 19. 删除链表的倒数第 N 个结点 | 中等 | 删除位置由倒数下标给出，需要快慢指针拉开固定间距一趟定位 |