LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.01
• 题目：3217.从链表中移除在数组中存在的节点
• 难度：中等
• 标签: 数组 链表 哈希表

1. 题目理解

问题描述：
给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。

示例：

示例 1： 输入： nums = [1,2,3], head = [1,2,3,4,5] 输出： [4,5] 解释：移除数值为 1, 2 和 3 的节点。

示例 2： 输入：nums = [7,13,11], head = [1,2,7,13,11,3,4] 输出：[1,2,3,4] 解释：移除数值为 7、13、11 的节点，保留其余节点并维持原有顺序。

2. 解题思路

核心观察

• 链表删除节点的关键是处理“前驱节点”与“后继节点”的连接，头节点删除需特殊处理。
• 数组查询的时间复杂度影响整体效率，直接遍历数组查询（O(n)）会导致整体复杂度偏高，需用哈希表优化为 O(1) 查询。

算法步骤

1. 哈希表构建：遍历 nums 数组，确定值的范围（minVal、maxVal），用动态数组模拟哈希表，标记 nums 中存在的值。
2. 虚拟头节点创建：创建 dummy 节点指向原链表头，统一头节点与中间节点的删除逻辑，避免单独处理头节点。
3. 链表遍历与删除：通过 cur 指针遍历链表，检查 cur->next 节点的值是否在哈希表中，若存在则删除该节点（跳过连接并释放内存），否则继续遍历。
4. 资源释放与返回：释放哈希表和 dummy 节点的内存，返回 dummy->next 作为新链表的头节点。

3. 代码实现

#include <stdlib.h> // 用于malloc、free

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* modifiedList(int* nums, int numsSize, struct ListNode* head) {
    // 1. 构建哈希表存储nums中的值，优化查询效率
    int maxVal = -1e9, minVal = 1e9;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > maxVal) maxVal = nums[i];
        if (nums[i] < minVal) minVal = nums[i];
    }
    int* hash = (int*)calloc(maxVal - minVal + 1, sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        hash[nums[i] - minVal] = 1; // 标记存在的数值
    }

    // 2. 创建虚拟头节点，统一处理头节点删除的情况
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* cur = dummy;

    // 3. 遍历链表，删除值在nums中的节点
    while (cur->next != NULL) {
        int val = cur->next->val;
        // 检查当前节点的值是否在nums中（通过哈希表O(1)查询）
        if (val >= minVal && val <= maxVal && hash[val - minVal]) {
            // 删除节点：跳过当前节点
            struct ListNode* temp = cur->next;
            cur->next = cur->next->next;
            free(temp); // 释放被删除节点的内存（可选，视题目要求）
        } else {
            // 不删除，继续下一个节点
            cur = cur->next;
        }
    }

    // 4. 释放哈希表，返回新的头节点（dummy->next）
    struct ListNode* newHead = dummy->next;
    free(hash);
    free(dummy);
    return newHead;
}

4. 代码优化说明

• 哈希表优化：用“数组模拟哈希表”替代直接遍历数组查询，将单次查询时间从 O(numsSize) 降至 O(1)，大幅提升效率。
• 虚拟头节点优化：避免单独处理头节点删除的边界情况（如原链表头节点需删除时），让所有节点的删除逻辑保持一致，代码更简洁。
• 内存管理优化：使用 calloc 初始化哈希表（默认值为 0），无需手动初始化；删除节点时释放内存，避免内存泄漏；最终释放哈希表和 dummy 节点，确保资源回收。
• 边界兼容优化：兼容空链表（head = NULL）、单节点链表、连续多个节点需删除等场景，无空指针异常风险。

5. 复杂度分析

• 时间复杂度：O(n + m)，其中 n 是链表的长度，m 是 nums 数组的长度。
  • 构建哈希表：遍历 nums 数组 2 次（找最值 + 标记存在值），时间为 O(m)。
  • 遍历链表：仅遍历链表一次，时间为 O(n)。
  • 整体无嵌套循环，时间复杂度为线性级别。
• 空间复杂度：O(k)，其中 k 是 nums 数组中值的范围（maxVal - minVal + 1）。
  • 哈希表占用的空间取决于 nums 中值的范围，最坏情况下（值范围极大）空间开销较高，但对于大部分场景（值范围适中）是高效的。
  • 其他变量（dummy、cur、temp 等）占用常数空间 O(1)。

6. 总结

本题的核心是“高效查询 + 链表节点删除”，关键优化点在于用哈希表降低查询复杂度，用虚拟头节点统一删除逻辑。解题时需注意边界情况（如头节点删除、空链表）和内存管理（避免内存泄漏）。

对于类似“链表筛选节点”的问题，可总结通用思路：

1. 若需频繁查询某个集合中的元素，优先用哈希表优化查询效率。
2. 链表删除节点时，虚拟头节点是简化逻辑的常用技巧。
3. 动态内存分配后需及时释放，避免资源浪费。