3217.从链表中移除在数组中存在的节点：哈希表(一次遍历)

【LetMeFly】3217.从链表中移除在数组中存在的节点：哈希表(一次遍历)

力扣题目链接：https://leetcode.cn/problems/delete-nodes-from-linked-list-present-in-array/

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

 

示例 1：

输入： nums = [1,2,3], head = [1,2,3,4,5]

输出： [4,5]

解释：

移除数值为 1, 2 和 3 的节点。

示例 2：

输入： nums = [1], head = [1,2,1,2,1,2]

输出： [2,2,2]

解释：

移除数值为 1 的节点。

示例 3：

输入： nums = [5], head = [1,2,3,4]

输出： [1,2,3,4]

解释：

链表中不存在值为 5 的节点。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• nums 中的所有元素都是唯一的。
• 链表中的节点数在 [1, 105] 的范围内。
• 1 <= Node.val <= 105
• 输入保证链表中至少有一个值没有在 nums 中出现过。

解题方法：哈希表

使用哈希表记录$nums$中都出现了哪些元素。

为了方便可以在链表第一个节点前设置一个一定不会被删除的没有实际值的“表头”，并使用两个变量$last$和$now$记录上一个遍历到的节点和当前节点。

在$now$不为空时，若$now$在$nums$中出现过，则扔掉$now$（更新$last$的$next$为$now$的$next$、$now$后移）；否则不删$now$（$last$和$now$都指向下一个节点）。

• 时间复杂度$O(len(nums) + len(list))$
• 空间复杂度$O(len(nums))$

AC代码

C++

/*
 * @LastEditTime: 2025-11-01 21:54:45
 */
/**
 * 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* modifiedList(vector<int>& nums, ListNode* now) {
        unordered_set<int> se(nums.begin(), nums.end());
        ListNode* head = new ListNode(0, now);  // 不可以：ListNode* head(0, now);  // Most Vexing Parse
        ListNode* last = head;
        while (now) {
            if (se.count(now->val)) {
                now = now->next;
                last->next = now;
            } else {
                last = now;
                now = now->next;
            }
        }
        return head->next;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源