移除链表元素

难度: Easy

给你一个链表的头节点 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

Submission

运行时间: 64 ms

内存: 17.9 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(next=head)
        pre = dummy
        cur = head
        while cur:
            if cur.val != val:
                pre = pre.next
            else:
                pre.next = cur.next
            cur = pre.next
        return dummy.next

Explain

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

时间复杂度: O(n)

空间复杂度: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # 创建虚拟头结点
        dummy = ListNode(next=head)
        # 初始化 pre 和 cur 指针
        pre = dummy
        cur = head
        # 遍历链表
        while cur:
            if cur.val != val:
                # 当前节点值不等于 val，pre 指针后移
                pre = pre.next
            else:
                # 当前节点值等于 val，删除节点
                pre.next = cur.next
            # cur 指针后移
            cur = pre.next
        # 返回新的头结点
        return dummy.next

Explore

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

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

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

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