Medium
题目描述
有一个单链表的头节点 head，我们想要删除它其中的一个节点 node。
给你一个需要删除的节点 node。你将无法访问第一个节点 head。
链表的所有值都是唯一的，题目保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。请注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
- node 前面的所有值顺序应该保持不变。
- node 后面的所有值顺序应该保持不变。
示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9
示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9
提示：
- 链表中节点的数目范围是 [2, 1000]
- -1000 <= Node.val <= 1000
- 链表中每个节点的值都是唯一的
- 需要删除的节点 node 是链表中的一个有效节点，且不是末尾节点
解题思路
这是一道经典的链表操作题，考查的是对链表删除操作的理解。
常规思路（无法实现）： 通常删除链表节点需要知道被删除节点的前驱节点，通过修改前驱节点的 next 指针来跳过要删除的节点。但本题只给定了要删除的节点，无法获取其前驱节点。
巧妙解法（推荐）： 既然无法删除当前节点，我们可以"偷梁换柱"：
- 将下一个节点的值复制到当前节点
- 删除下一个节点
这样从外部看来，就好像删除了当前节点一样。由于题目保证要删除的节点不是最后一个节点，所以一定存在下一个节点。
实现步骤：
node.val = node.next.val- 用下一个节点的值覆盖当前节点的值node.next = node.next.next- 跳过下一个节点，完成删除
时间复杂度 O(1)，空间复杂度 O(1)，这是最优解法。
代码实现
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};
class Solution:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
public class Solution {
public void DeleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
var deleteNode = function(node) {
node.val = node.next.val;
node.next = node.next.next;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(1) | 只需要常数时间的赋值操作 |
| 空间复杂度 | O(1) | 只使用常数额外空间 |