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