203.移除链表元素

一、 问题描述

删除链表中等于给定值 val 的所有节点。

示例

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

二、方案一：迭代法

1、思路

• 使用一个哑节点作为新链表的头部，这样可以避免处理头部节点的特殊情况。
• 遍历链表，当当前节点的下一个节点的值等于 val 时，跳过这个节点。

2、代码实现

func removeElements(head *ListNode, val int) *ListNode {
    // 创建哨兵节点，其Next指向head
    sentinel := &ListNode{Next: head}
    // 初始化当前节点为哨兵节点
    current := sentinel
    // 遍历链表
    for current.Next != nil {
        // 如果当前节点的下一个节点的值等于给定值
        if current.Next.Val == val {
            // 跳过这个节点
            current.Next = current.Next.Next
        } else {
            // 否则，移动到下一个节点
            current = current.Next
        }
    }
    // 返回哨兵节点的下一个节点作为新链表的头部
    return sentinel.Next
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。
• 空间复杂度：O(1)。

三、方案二：递归法

1、思路

• 递归的基本思想是先处理子问题，然后再处理当前问题。
• 对于当前节点，先递归地移除其所有子节点中的 val。
• 然后判断当前节点的值是否等于 val，如果是，则返回其下一个节点；否则，返回当前节点。

2、代码实现

func removeElements(head *ListNode, val int) *ListNode {
    // 如果链表为空，直接返回空
    if head == nil {
        return nil
    }
    // 递归地删除头节点的下一个节点
    head.Next = removeElements(head.Next, val)
    // 如果头节点的值等于给定值，返回头节点的下一个节点
    // 否则，返回头节点
    return head.Val == val ? head.Next : head
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。
• 空间复杂度：O(n)，递归栈的深度。

四、总结

方案	时间复杂度	空间复杂度	备注
迭代法	O(n)	O(1)	使用哑节点简化操作
递归法	O(n)	O(n)	递归实现，代码简洁

迭代法在空间复杂度上更优，递归法在代码简洁性上更优。根据实际情况选择适合的方法。