237. 删除链表中的节点

1. 题目简介

难度：中等，原题链接：237. 删除链表中的节点。

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

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

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

2. 问题分析

只有目标节点 node，无法找到它的前驱，就不能通过修改前驱的 next 来删除它。但题目保证 node 不是尾节点，因此可以用后继节点的值覆盖当前值，再跳过后继节点。

具体分为两步：先执行 node.val = node.next.val，再执行 node.next = node.next.next。这里是复制后继的值，不需要交换两个值。

例如链表 4 → 5 → 1 → 9 中，要删除值为 5 的节点。先把它的值改为 1，再跳过原来值为 1 的后继节点，得到 4 → 1 → 9。目标节点对象仍然留在链表中，被解除链接的是后继节点，但从值的序列来看，目标值已经被删除。

如果 node 是尾节点，就没有后继可以复制和跳过，所以“不是最后一个节点”是这种做法成立的必要条件。

3. 代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        // 修改当前 node 的 val，即可让当前 node 替换掉下一个 node
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

4. 复杂度分析

• 时间复杂度：O(1)，只需要修改当前节点的值和指针。
• 空间复杂度：O(1)，不需要额外的空间。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明