题目信息

  • 平台：LeetCode
  • 题目：203. 移除链表元素
  • 难度：简单
  • 题目链接：移除链表元素

题目描述

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

初步思路

核心是删除链表中值等于 val 的所有节点。链表操作的难点在于：

  1. 头节点的处理：如果头节点本身就是要删除的节点，需要特殊处理
  2. 节点删除：删除某个节点需要知道它的前驱节点

我们可以有三种思路来解决这个问题：

  1. 分类讨论：分别处理头节点和非头节点
  2. 虚拟头节点：添加一个 dummy head，统一所有节点的处理逻辑
  3. 递归：利用递归的特性，从后往前处理节点

算法分析

方法一：分类讨论

  • 核心思想：先处理头节点，再处理非头节点
  • 技巧要点：
    1. 用 while 循环删除所有需要删除的头节点（可能连续多个）
    2. 用 cur 指针遍历链表，检查 cur->next 是否需要删除
    3. 删除节点时需要保存临时指针以便释放内存
  • 时间复杂度：**O(n)**，只需遍历链表一次
  • 空间复杂度：**O(1)**，只使用常数额外空间

方法二：虚拟头节点（推荐）

  • 核心思想：在链表头添加一个虚拟节点，使所有节点的处理逻辑统一
  • 技巧要点：
    1. 创建 dummy_head，其 next 指向原头节点
    2. 从 dummy_head 开始遍历，检查 cur->next
    3. 最后返回 dummy_head->next 作为新头节点，记得释放 dummy_head
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

方法三：递归

  • 核心思想：利用递归从后往前处理节点
  • 技巧要点：
    1. 递归终止条件：当前节点为空，返回 nullptr
    2. 先递归处理 head->next
    3. 根据当前节点值是否等于 val 决定是否保留当前节点
  • 时间复杂度：O(n)
  • 空间复杂度：**O(n)**，递归栈深度最坏为 n

代码实现（C++）

方法一：分类讨论

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头节点
        while (head != nullptr && head->val == val) {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }
        // 删除非头节点
        ListNode* cur = head;
        while (cur != nullptr && cur->next != nullptr) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

方法二：虚拟头节点（推荐）

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy_head = new ListNode(0, head);

        ListNode* cur = dummy_head;
        while (cur != nullptr && cur->next != nullptr) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummy_head->next;
        delete dummy_head;
        return head;
    }
};

方法三：递归

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) {
            return nullptr;
        }
        // 递归处理后续节点
        if (head->val == val) {
            ListNode* tmp = head;
            head = removeElements(head->next, val);
            delete tmp;
            return head;
        } else {
            head->next = removeElements(head->next, val);
            return head;
        }
    }
};

测试用例

输入 输出 说明
head = [1,2,6,3,4,5,6], val = 6 [1,2,3,4,5] 删除中间和末尾的 6
head = [], val = 1 [] 空链表直接返回
head = [7,7,7,7], val = 7 [] 所有节点都要删除

总结与反思

链表操作的关键在于处理前驱节点。虚拟头节点是一个非常实用的技巧，它能让我们避免单独处理头节点的情况，使代码更加简洁统一。

三种方法各有特点：

  • 分类讨论：思路直接，但代码稍显冗长
  • 虚拟头节点：推荐做法，代码简洁优雅
  • 递归：代码最简洁，但会产生额外的栈空间开销

在实际面试中，虚拟头节点的方法通常是最优选择，既高效又容易实现。另外，记得在 C++ 中手动释放删除的节点内存，避免内存泄漏。