第五天打卡：移除链表元素

张开发
• 2026/4/18 19:51:49 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

第五天打卡：移除链表元素
今天是算法打卡的第五天选择了一道经典的链表操作题移除链表元素。这道题看似简单但其中涉及的边界条件处理和递归思维非常值得深入探讨。希望通过这篇博客记录下解题过程和思考。题目描述给你一个链表的头节点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 500 val 50解题思路这道题的核心是遍历链表并删除指定值的节点。常见的解法有两种迭代法和递归法。这里我选择了递归法代码更简洁但需要理解递归的“回溯”过程。递归思路终止条件当head null时直接返回null空链表或遍历到末尾。递归处理先递归处理head.next将处理后的子链表赋值给head.next。判断当前节点若head.val val则跳过当前节点返回head.next否则保留当前节点返回head。关键点递归的本质是“从后往前”处理链表。先处理完子链表再决定当前节点是否保留避免了迭代法中需要维护前驱节点的麻烦。代码实现复杂度分析时间复杂度O(n)其中n为链表长度。每个节点仅被访问一次。空间复杂度O(n)递归调用栈的深度最多为n最坏情况链表为单链。总结通过这道题我深刻体会到递归在链表操作中的优雅性。虽然递归的空间复杂度较高但代码简洁且逻辑清晰。后续可以尝试用迭代法实现对比两种解法的优劣。

更多文章