0237. Delete Node in a Linked List¶
题目信息¶
- 题号:
0237
- 难度:
Medium
- 主题:
单链表、原地修改、节点接口
- 原题:
- 重点:
只给待删除节点而不给头节点、目标不是尾节点、值唯一、函数无返回值
题目重述¶
有一条单链表,但函数不会得到链表头节点,只会得到需要删除的节点 node。需要原地修改链表,使从原头节点遍历得到的结果中不再出现 node 原先代表的元素,并且其他节点值保持原来的相对顺序。函数返回类型为 void。
链表节点数位于 [2, 1000],节点值位于 [-1000, 1000] 且互不相同。题目保证传入节点属于该链表,并且它不是尾节点,因此它一定存在后继节点。调用者不会通过返回值获得新头节点,修改结果必须体现在现有链表对象上。
自建示例¶
删除中间节点:
输入:原链表为 [6, 3, 9, 4],传入值为 3 的节点
输出:链表变为 [6, 9, 4]
解释:函数没有获得头节点,但调用结束后从原头遍历时,值 3 已消失,其余值的顺序仍为 6、9、4。
删除倒数第二个节点:
输入:原链表为 [1, 8, 5],传入值为 8 的节点
输出:链表变为 [1, 5]
解释:目标节点不是尾节点,删除后尾部元素 5 仍保留在链表中。
把后继内容搬到当前节点¶
没有头节点和前驱指针时,无法直接把传入节点从前驱的 next 中摘掉;题目又保证它不是尾节点,
因此可以利用它的后继:
node -> successor -> successor.next
先把 successor->val 复制到 node->val,再令 node->next = successor->next。
从原头节点遍历时,原节点的值被后继值替代,后继节点被跳过,观察到的值序列正好等于删除目标后的序列。
这是一种“逻辑删除”:传入的节点对象仍然在链表中,但它已经承载了后继节点的值;真正从可达链中摘掉的是后继对象。 若使用带明确所有权的自建链表,可在重接后释放被摘掉的后继;在线评测的节点生命周期通常由平台管理,不在函数中手动释放。
正确性说明¶
目标节点不是尾节点,所以 node->next 一定存在。复制后继值不会改变目标前面的任何节点,
也不会改变后继之后的节点及其相对顺序;跳过后继只减少一个节点的可达性。于是从头遍历得到的序列,
恰好删除了原目标值并保留其余值的顺序。因为题目保证节点值唯一,复制后继值不会产生另一个相同值的歧义。
C++ 实现¶
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode* successor = node->next;
node->val = successor->val;
node->next = successor->next;
}
};
代码分析¶
函数只访问目标及其后继,时间复杂度和额外空间均为 O(1)。不能把 node 设为 nullptr,
因为前驱仍然指向它;也不能调用需要前驱的常规删除流程。代码不返回新头节点,修改通过原链表入口对调用者可见。