LeetCode 面试题 02.03. 删除中间节点
题目描述
题意分析
只给出单链表中待删除节点
node，没有头节点，也无法直接访问它的前驱。题目保证该节点不是尾节点，要求修改链表，使最终的值序列与删除这个位置一致。普通删除需要让前驱跳过当前节点，但这里拿不到前驱。可利用必然存在的后继，让当前节点接替后继的值，再把后继移出链表，达到相同的序列效果。
解法：复制后继节点并跳过
核心思路
[!blue]
当前节点之前的连接无法修改，因此保留当前节点对象，先把
node.next.val复制给node.val。这样当前逻辑位置变成了原来的下一个值，但后面还保留着同样的后继值，需要再跳过原后继。执行
node.next = node.next.next后，当前节点直接接到原后继之后的部分。前面的节点仍连接到当前对象，后面的顺序也保持不变，最终只少了原当前位置上的值，效果等价于删除目标位置。实际移出链表的是后继对象，当前对象继续存在，这与必须删除某个特定对象身份的要求不同。题目的非尾保证是关键：如果当前节点没有后继，就无法复制后继值，也无法在缺少前驱的情况下让前面的连接断开。
两个赋值顺序不能颠倒，先读取后继值，再跳过后继，才能保留正确数据。只把局部变量
node改为后继，也不会改变外部链表中的任何值或连接。
解题步骤
- 将后继节点的值复制到当前节点。
- 将当前节点的
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)$，不创建新节点。
关键点总结
[!green]
- 非尾节点保证后继存在，是方法成立的前提。
- 先读取后继值，再修改连接，顺序不能交换。
- 题目判断的是最终值序列，不要求移除当前对象本身。
易错点总结
[!yellow]
- 仅执行
node = node.next：只改变局部变量，外部链表不变。- 只改
next：删除的是后继，当前节点原来的值还在。- 颠倒两行顺序：跳过后继后再复制，会读取错误节点，甚至访问空指针。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！