LeetCode题练习与总结：删除链表中的节点--237

一、题目描述

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

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

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

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

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

自定义测试：

对于输入，你应该提供整个链表 head 和要给出的节点 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 是 链表中的节点 ，且 不是末尾节点

二、解题思路

由于我们无法访问链表的第一个节点，且只能访问需要删除的节点，我们不能直接删除该节点，因为这样会导致无法访问后续节点。但是，我们可以采取一种巧妙的方法：将需要删除的节点的下一个节点的值复制到需要删除的节点，然后删除下一个节点。

具体步骤如下：

将给定节点（node）的下一个节点（node.next）的值复制到给定节点。
将给定节点的 next 指针指向下一个节点的下一个节点（node.next.next）。
删除下一个节点（即原本需要删除的节点的下一个节点），这可以通过将给定节点的 next 指针指向下下个节点来实现。

三、具体代码

class Solution {public void deleteNode(ListNode node) {// 将下一个节点的值复制到当前节点node.val = node.next.val;// 删除下一个节点，即将当前节点的next指针指向下下个节点node.next = node.next.next;}
}

这样，我们就实现了删除链表中的指定节点，而无需访问链表的头节点。需要注意的是，题目已经保证了 node 不是链表的最后一个节点，因此 node.next 一定不为空，这样我们的操作才是安全的。

四、时间复杂度和空间复杂度

1. 时间复杂度

该算法包含的操作步骤如下：

将下一个节点的值复制到当前节点：这是一个赋值操作，其时间复杂度为 O(1)。
将当前节点的 next 指针指向下下个节点：这也是一个赋值操作，其时间复杂度为 O(1)。

这两个操作都是常数时间操作，并且没有循环或者递归调用，因此整个函数的时间复杂度为 O(1)，即常数时间复杂度。

2. 空间复杂度

在执行删除操作的过程中，我们没有使用额外的数据结构来存储链表中的节点或者节点的值。我们仅仅是改变了节点的值和指针的指向，没有引入新的内存分配。

因此，算法的空间复杂度为 O(1)，即常数空间复杂度。

该算法的时间复杂度和空间复杂度都非常低，这是因为算法直接在链表上操作，而不需要遍历整个链表，也不需要额外的存储空间。

五、总结知识点

链表（Linked List）：
- 链表是一种常见的基础数据结构，由一系列节点（Node）组成。
- 每个节点包含数据域（value）和指向下一个节点的指针（next）。
节点（Node）：
- 在链表中，每个元素被封装为一个节点。
- 节点通常包含两个部分：数据部分（本例中为 int val）和指针部分（本例中为 ListNode next）。
指针（Pointer）：
- 在Java中，指针的概念通过引用（Reference）实现。
- ListNode next 是一个指向下一个节点的引用。
引用（Reference）：
- Java中的引用用于访问内存中的对象。
- 在本例中，node.next 是一个引用，指向当前节点的下一个节点。
赋值操作（Assignment）：
- node.val = node.next.val; 是一个赋值操作，将下一个节点的值复制到当前节点。
链表操作：
- 链表操作通常涉及指针的更改，而不涉及数据本身的复制。
- 在本例中，通过改变指针的指向来实现节点的“删除”。
删除操作：
- 在本例中，删除操作实际上是通过改变指针来跳过要删除的节点，而不是从内存中删除节点。