題目

3217. Delete Nodes From Linked List Present in Array
難度: 中等

題意

給定一個鏈結串列head與一整數陣列nums代表要刪除的值。
若此鏈結串列的節點之值包含在nums中，則刪除該節點。

方向

如同昨天提到的，這題需要反覆查詢nums是否存在某值，因此應膝跳反射想到用哈希表來解。

• 用三個指標前一個節點，目前節點、下一個節點，來遍歷整個鏈結串列。
• • 若目前節點的值存在於nums，則將前一個沒被移除的節點的下一個節點指標，更改為目前節點的下一個節點指標；接著刪除目前節點
• • 若不存在目前節點的值不存在於nums，則依序更新三個指標

技巧1: 可以創建一個虛設節點指向鏈結串列的頭，方便我們操作三個指標；最後回傳虛設節點的下一個節點指標即為所求之頭。
技巧2: 在leetcode上，刪除的節點要不要delete(CPP)或是free(C)都是可以AC的，有得時候不free掉會比較快。

實作

class Solution
{
public:
    ListNode *modifiedList(vector<int> &nums, ListNode *head)
    {
        unordered_set<int> nums_set;
        for (auto num : nums)
            nums_set.insert(num);
        
        // Create a dummy head;
        ListNode dummy_node = ListNode(0, head);
        ListNode *prev_node = &dummy_node;
        ListNode *curr_node = head;
        ListNode *next_node = nullptr;

        while(curr_node)
        {
            next_node = curr_node->next;

            if(nums_set.find(curr_node->val) != nums_set.end())
            {
                prev_node->next = next_node;
                delete curr_node;
                curr_node = next_node;
            }
            else
            {
                prev_node = curr_node;
                curr_node = next_node;
            }
        }

        return dummy_node.next;
    }
};

分析

若鏈結串列長度為N，nums長度為M
時間複雜度: O(M+N)；建立長度M的哈希表，遍歷長度N的鏈結串列
空間複雜度: O(M)，需要建立長度M的哈希表，三個指標和一個虛設指標來遍歷鏈結串列。

結果

582/582 cases passed (443 ms)
Your runtime beats 57.29 % of cpp submissions
Your memory usage beats 71.2 % of cpp submissions (258.5 MB)