LeetCode 第237题：删除链表中的节点

题目描述

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

• 给定节点的值不应该存在于链表中。
• 链表中的节点数应该减少 1。
• node 前面的所有值顺序相同。
• node 后面的所有值顺序相同。

自定义测试：

• 对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而且它的值不应该与任何其他节点相同。
• 我们将构建链表，并将节点传递给你的函数。
• 输出将是调用你函数后的整个链表。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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 指针，跳过待删除的节点。但在这道题中，这种常规方法是行不通的。

我们可以采用一种巧妙的方法来解决这个问题：

1. 将待删除节点的下一个节点的值复制到当前节点。
2. 然后将当前节点的 next 指针指向下下个节点，相当于删除了下一个节点。
3. 这样就相当于删除了当前节点，因为当前节点的值已经被修改为下一个节点的值。

这种方法之所以可行，是因为题目明确说明了待删除节点不是链表的最后一个节点，所以一定存在下一个节点供我们复制值。

方法：直接修改当前节点

时间复杂度：O(1)，只需要进行几个简单的指针操作。 空间复杂度：O(1)，不需要额外的空间。

代码实现

C# 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void DeleteNode(ListNode node) {
        // 将下一个节点的值复制到当前节点
        node.val = node.next.val;
        // 将当前节点的next指针指向下下个节点，跳过下一个节点
        node.next = node.next.next;
    }
}

Python 实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # 将下一个节点的值复制到当前节点
        node.val = node.next.val
        # 将当前节点的next指针指向下下个节点，跳过下一个节点
        node.next = node.next.next

C++ 实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        // 将下一个节点的值复制到当前节点
        node->val = node->next->val;
        // 将当前节点的next指针指向下下个节点，跳过下一个节点
        ListNode* temp = node->next;
        node->next = node->next->next;
        // 可选：释放被删除节点的内存
        delete temp;
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	说明
C#	88 ms	37.9 MB	简单的指针操作
Python	36 ms	16.1 MB	Python的实现非常简洁
C++	8 ms	7.5 MB	C++实现效率最高，可以手动释放内存

补充说明

代码亮点

1. 解法巧妙地绕过了无法访问前一个节点的限制
2. 所有实现都达到了O(1)的时间复杂度
3. 代码简洁，只需几行就能完成

优化方向

1. 在C++实现中可以选择是否释放被删除节点的内存
2. 由于题目条件限制严格（节点不是末尾节点，值唯一），代码没有额外的检查逻辑，保持了简洁

解题难点

1. 理解如何在不访问头节点或前一个节点的情况下删除当前节点
2. 认识到可以通过修改节点值和指针结构来“模拟”删除操作

常见错误

1. 试图使用常规的链表删除方法，查找前一个节点
2. 忘记考虑内存释放（在手动管理内存的语言中）
3. 对删除最后一个节点的情况处理不当（题目保证不会出现这种情况）

相关题目

• 203. 移除链表元素 - 移除链表中所有指定值的节点
• 83. 删除排序链表中的重复元素 - 删除排序链表中的重复元素
• 19. 删除链表的倒数第 N 个结点 - 删除链表的倒数第 N 个节点
• 206. 反转链表 - 反转单链表