企业官网建设流程全解析

今天是算法打卡的第五天，选择了一道经典的链表操作题：移除链表元素。这道题看似简单，但其中涉及的边界条件处理和递归思维非常值得深入探讨。希望通过这篇博客，记录下解题过程和思考。

题目描述

给你一个链表的头节点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^4]内
• 1 <= Node.val <= 50
• 0 <= val <= 50

解题思路

这道题的核心是遍历链表并删除指定值的节点。常见的解法有两种：迭代法和递归法。这里我选择了递归法，代码更简洁，但需要理解递归的“回溯”过程。

递归思路：

1. 终止条件：当head == null时，直接返回null（空链表或遍历到末尾）。
2. 递归处理：先递归处理head.next，将处理后的子链表赋值给head.next。
3. 判断当前节点：若head.val == val，则跳过当前节点（返回head.next）；否则保留当前节点（返回head）。

关键点：递归的本质是“从后往前”处理链表。先处理完子链表，再决定当前节点是否保留，避免了迭代法中需要维护前驱节点的麻烦。

代码实现

复杂度分析

• 时间复杂度：O(n)，其中n为链表长度。每个节点仅被访问一次。
• 空间复杂度：O(n)，递归调用栈的深度最多为n（最坏情况链表为单链）。

总结

通过这道题，我深刻体会到递归在链表操作中的优雅性。虽然递归的空间复杂度较高，但代码简洁且逻辑清晰。后续可以尝试用迭代法实现，对比两种解法的优劣。