删除链表中的节点
难度:
标签:
题目描述
有一个单链表的 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是 链表中的节点 ，且 不是末尾节点
代码结果
运行时间: 40 ms, 内存: 15.3 MB
/*
* 思路：
* 使用Java Stream不能直接操作链表结构，因此我们先将链表转为List进行操作。
* 然后找到要删除的节点，通过跳过该节点来完成删除。
*/
import java.util.List;
import java.util.stream.Collectors;
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class Solution {
public List<Integer> deleteNode(ListNode head, int target) {
List<Integer> list = convertToList(head);
return list.stream()
.filter(val -> val != target)
.collect(Collectors.toList());
}
private List<Integer> convertToList(ListNode head) {
List<Integer> list = new ArrayList<>();
ListNode current = head;
while (current != null) {
list.add(current.val);
current = current.next;
}
return list;
}
}
解释
方法:
这个题解的思路是直接将要删除节点的值替换为下一个节点的值，然后删除下一个节点。这样可以在无法访问头节点的情况下，通过修改要删除节点的值和next指针来达到删除节点的目的。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中，你是如何确保`node.next`不为`None`，也就是说，`node`不是链表中的最后一个节点？
▷🦆
题解中提到了将要删除的节点的值替换为下一个节点的值，这种方法是否会导致链表中出现两个连续的相同值？
▷🦆
进行节点删除后，题解是否考虑了对下一个节点的内存进行释放或其他资源管理措施？
▷🦆
如果链表只有两个节点，且要删除的是第一个节点，题解的方法是否还适用？
▷