移除链表元素

难度:

标签:

题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 10⁴] 内
1 <= Node.val <= 50
0 <= val <= 50

代码结果

运行时间: 64 ms, 内存: 17.9 MB

/*
 * Problem: Given a linked list and a value, remove all the nodes with the value from the list.
 * The function should return the new head of the list.
 *
 * Approach using Java Streams:
 * 1. Convert the linked list to a stream of nodes.
 * 2. Filter out the nodes with the target value.
 * 3. Collect the filtered nodes back into a linked list.
 */
 
import java.util.stream.*;
import java.util.*;
 
public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Convert linked list to a list
        List<ListNode> nodeList = new ArrayList<>();
        while (head != null) {
            nodeList.add(head);
            head = head.next;
        }
 
        // Filter nodes with value not equal to val
        List<ListNode> filteredList = nodeList.stream()
            .filter(node -> node.val != val)
            .collect(Collectors.toList());
 
        // Reconstruct the linked list from the filtered list
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (ListNode node : filteredList) {
            current.next = node;
            current = current.next;
        }
        // Terminate the list
        current.next = null;
 
        return dummy.next;
    }
}

解释

方法:

这个题解使用了虚拟头结点（dummy node）的技巧来简化删除操作。具体思路如下： 1. 创建一个虚拟头结点 dummy，将其 next 指针指向链表的真正头结点 head。 2. 定义两个指针 pre 和 cur，分别指向虚拟头结点 dummy 和真正的头结点 head。 3. 遍历链表，当 cur 指向的节点值不等于给定的 val 时，将 pre 指针向后移动；否则，将 pre 的 next 指针指向 cur 的下一个节点，实现删除操作。 4. 最后返回虚拟头结点的 next 指针，即为删除操作后的新链表的头结点。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

虚拟头结点（dummy node）的作用是什么，为什么在这个问题中使用它可以简化删除头结点的操作？

▷

虚拟头结点（dummy node）主要用于简化链表操作，特别是当操作涉及到头结点的变更时。在删除头结点的场景中，如果头结点本身就需要被删除（例如其值等于目标值val），直接操作头结点会使得需要额外的判断和处理来更新新的头结点。使用虚拟头结点可以统一操作逻辑，无论是删除头结点还是中间的节点，处理方式都相同，即通过调整前驱节点（即dummy的next指针）来删除当前节点。这样就避免了在链表头部进行特殊处理，简化了代码的复杂性。

🦆

在删除节点时，您没有更新`cur`指针的位置（即`cur = cur.next`），这是否会影响循环的逻辑或导致遗漏节点？

▷

在题解中，确实存在一个错误。更新`pre.next`后应当直接移动`cur`指针到`pre.next`，而不是到`cur.next`（这在题解中未明确指出，应为`cur = pre.next`）。如果不这样做，将导致`cur`指针错过检查新的当前节点（即`pre.next`），特别是在处理连续需要删除的节点时。因此，正确的逻辑应该是在每次循环的末尾将`cur`更新为`pre.next`，确保`cur`总是指向`pre`之后的节点，从而不会错过任何节点的检查。

🦆

如何处理链表中连续的多个节点值等于`val`的情况？请说明您的代码在处理这种情况时的具体行为。

▷

在处理连续多个节点的值等于`val`的情况时，由于使用了虚拟头结点和正确的指针更新逻辑（假设已修正`cur = pre.next`的问题），代码可以正确处理这种情况。当`cur`指向的节点值等于`val`时，`pre.next`会被更新为`cur.next`，从而跳过当前`cur`节点。循环继续，`cur`更新为`pre.next`。这个过程会连续执行，直到`cur`指向的节点的值不等于`val`。因此，不管是单个还是连续多个需要删除的节点，都会被正确地从链表中移除。

🦆

在返回新链表的头结点时，直接返回`dummy.next`是否安全？是否存在`dummy.next`仍指向原链表的风险？

▷

直接返回`dummy.next`是安全的，并且是这种方法的标准做法。`dummy`节点是作为新链表的固定头部存在的，它的`next`指针始终指向链表的实际头结点（即第一个不被删除的节点）。即使全部节点都被删除，`dummy.next`也将正确地更新为`null`，表示新链表为空。因此，不存在`dummy.next`仍指向原始链表导致数据不一致的风险。这种方法保证了操作的安全性和正确性。

相关问题

移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

删除链表中的节点

有一个单链表的 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 是 链表中的节点 ，且 不是末尾节点

快乐数计数质数