# LeetCode 3217. Delete Nodes From Linked List Present in Array

https://leetcode.com/problems/delete-nodes-from-linked-list-present-in-array/description/

## 題目大意

給一個 linked list 跟整數陣列 `nums`
把 `nums` 中有出現的數字從 linked list 中移除並回傳新的串列頭

Constraints:

- $1\le$ `nums.length` $\le 10^5$
- $1\le$ `nums[i]` $\le 10^5$
- `nums` 中的元素全相異
- linked list 中的元素值範圍在 $[1, 10^5]$.
- $1\le$ `Node.val` $\le 10^5$
- 測資提供的 linked list 必至少一個節點的值不在 `nums` 中

## 思考

這題不難，兩個重點會就輕輕鬆鬆

1. 快速查找節點值是否在 `nums` 中
2. 刪除節點

這邊再次給不熟悉資料結構的做簡單說明

先談查找，以時間複雜度作為理論依據來說，我們要在陣列中尋找到某個值的時間複雜度是 $O(m)$ ，其中 `m` 為 `nums.size()`
我們要想刪除 linked list 中的節點，由於我們只有 `head` 的位置，所以我們勢必要從頭到尾遍歷 linked list 一遍，若 linked list 長度為 `n` 則我們每到達一個節點就要花費 $O(m)$ 的時間確認 `Node.val` 是否在 `nums` 中
這樣的時間複雜度是 $O(mn)$

所以一個相當直觀的想法是，我們可以事先確認 `nums` 都有哪些值

如果我們使用 `unordered_set` 來記錄：

unordered_set<int> numSet(nums.begin(), nums.end());

插入的平均時間複雜度為 $O(1)$ ，所以建立表的時間是 $O(m)$
查找的平均複雜度我們也能視為 $O(1)$ ，遍歷的時候我們每次只花 $O(1)$，所以我們所以查找整條 linked list 也就花 $O(n)$

numSet.find(curr->next->val) != numSet.end() // set 的查找，如果沒找到，值就會是 numSet.end()

時間複雜度這樣下來變成了 $O(m+n)$

以演算法來說，回答到這就已經相當不錯，可以交卷了
不過使用 `unordered_set` 有個問題，那就是它的原理實際依賴 hash table ，這個的原理簡單來說就是透過設計好的 hash function 在平均來說 $O(1)$ 之下得到資料的索引
然而，在最壞的情況下，查找可能會退化回線性

由於這題我們只是需要知道 `Node.val` **是否**在 `nums` 中
所以一個更好的選擇是用 `bitset`

時間複雜度來看兩個選擇的演算法是一樣的
然而以這題來說，我們會發現基於位運算的 `bitset` 時間表現上會更好一些

以下為最後的參考解答

class Solution
{
public:
    ListNode *modifiedList(vector<int> &nums, ListNode *head)
    {
        bitset<100001> bitSet;

        for (int num : nums)
        {
            bitSet.set(num);
        }

        ListNode *dummy = new ListNode(0, head);
        ListNode *curr = dummy;

        while (curr->next)
        {
            if (bitSet[curr->next->val])
                curr->next = curr->next->next;
            else
                curr = curr->next;
        }

        return dummy->next;
    }
};

這邊用了 linked list 的一個小技巧，就是設一個 dummy node (在 `head` 前新加一個沒有要用的節點，這樣我們永遠看當前節點的下一個節點就好，也就是 `curr->next`)
這樣下面寫 code 會比較簡潔好寫