203. 移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/

题目

给你一个链表的头节点 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 输出：[]

思路一（虚拟头节点法）

处理链表删除问题时，头节点可能需要被删除（如示例3），直接操作原头节点会增加边界处理复杂度。因此采用**虚拟头节点（哨兵节点）**优化，统一所有节点的删除逻辑：

1. 创建虚拟头节点 dummy，使其 next 指向原链表头节点 head，让原链表所有节点（包括头节点）都拥有统一的前驱节点；
2. 定义遍历指针 cur，初始指向 dummy，通过 cur.next 访问并遍历后续实际节点，避免直接修改头节点带来的边界问题；
3. 遍历过程中，若 cur.next.val == val，则通过 cur.next = cur.next.next 跳过该节点，实现删除；若无需删除，则移动 cur 指针继续遍历下一个节点；
4. 遍历结束后，dummy.next 即为删除操作后的新头节点，无需担心原头节点被删除后无法返回有效节点。

该思路时间复杂度为 O(n)（n为链表节点数，仅需一次线性遍历），空间复杂度为 O(1)（仅使用常数级额外空间，无额外数据结构）。

解法一（虚拟头节点法）

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(0)
        dummy.next = head
        cur = dummy
        while cur.next is not None:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next

解释一（虚拟头节点法代码解释）

思路二（递归法）

利用递归的分治思想，将链表删除问题拆解为“当前节点处理”和“剩余链表处理”的子问题，从链表尾部向前倒序完成删除：

1. 递归终止条件：当 head 为 None 时，说明已遍历到链表尾部，空链表无需删除操作，直接返回 None；
2. 递归处理子问题：先递归调用函数处理当前节点的后继链表 head.next，将处理后的后继链表头节点赋值给 head.next，实现从链表尾部向前的倒序处理；
3. 当前节点判断：处理完后继链表后，判断当前节点值是否等于目标值 val，若相等则当前节点需要删除，返回处理后的后继链表头节点（即 head.next）；若不相等则当前节点保留，返回当前节点 head；
4. 递归回溯：每一层递归返回的结果会作为上一层节点的后继节点，最终回溯到链表头部时，得到完整的删除后新链表。

该思路时间复杂度为 O(n)（每个节点仅被访问一次，线性遍历），空间复杂度为 O(n)（最坏情况下，链表无需要删除的节点，递归调用栈深度等于链表长度n）。

解法二（递归法）

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:
        if head is None:
            return None
        head.next = self.removeElements(head.next, val)
        return head.next if head.val == val else head

解释二（递归法代码解释）