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;是一个赋值操作，将下一个节点的值复制到当前节点。
-
链表操作：
- 链表操作通常涉及指针的更改，而不涉及数据本身的复制。
- 在本例中，通过改变指针的指向来实现节点的“删除”。
-
删除操作：
- 在本例中，删除操作实际上是通过改变指针来跳过要删除的节点，而不是从内存中删除节点。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。