题目详情

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

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

示例 2：

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

输出： [2,2,2]

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

提示：

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

解法一：暴力查找法

看到题目的第一反应是，暴力破解，用双指针扫描链表，将扫描到的链表的值与数组中的值一一比较，存在相同值则删除该节点，并将指针后移。具体代码实现如下：

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

struct ListNode* modifiedList(int* nums, int numsSize, struct ListNode* head) {
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode)); //哨兵节点
    dummy->next = head;
    struct ListNode *pre = dummy; //前驱指针
    struct ListNode *cur = head; //当前指针
    int flag = 0; // flag标记当前节点是否需要删除
    while(cur != NULL){
        flag = 0;
             // 检查当前节点值是否在nums数组中
        for(int i = 0; i < numsSize; i++){
            if(cur->val == nums[i]){
                flag = 1; // 标记需要删除
                        //// 删除当前节点
                pre->next = cur->next;
                cur = cur->next;
                break;
            }
        }
        if(!flag){
                  // 若未进行删除操作，正常移动指针
            pre = cur;
            cur = cur->next;
        }
    }
    struct ListNode *ret = dummy->next;
    free(dummy);
    return ret;
}

对于该算法，每一个链表元素都要遍历nums数组进行查找，时间复杂度为O(nm)，提交时不出意外的超时了。 于是在查看了评论区以及查找了哈希表相关内容后，用哈希表进行了优化

解法二：哈希表法（推荐）

解题思路

针对解法一的性能瓶颈，我们可以使用哈希表来优化查找过程。由于题目限制节点值范围在[1, 10^5]，我们可以使用数组来模拟哈希表，将数组的查找时间从O(m)优化到O(1)。

算法步骤

1. 预处理：创建哈希表，标记所有需要删除的值
2. 遍历删除：使用双指针遍历链表，通过哈希表O(1)时间判断是否删除
3. 返回结果：返回处理后的链表头节点

C:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* modifiedList(int* nums, int numsSize, struct ListNode* head) {
    if (numsSize == 0) return head;
    // 创建哈希表（数组模拟），范围[1, 100000]
    int HashMap[100001];
    memset(HashMap, 0, sizeof(HashMap));
    // 将需要删除的值标记在哈希表中
    for(int i = 0; i < numsSize; i++){
        HashMap[nums[i]]++;
    }

    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->next = head;
    // 双指针遍历
    struct ListNode *pre = dummy;
    struct ListNode *cur = head;
    while(cur != NULL){
        // O(1)时间查找当前节点是否需要删除
        if(HashMap[cur->val] > 0){
        pre->next = cur->next;
        cur = cur->next;
            }else{
                // 不需要删除：正常移动指针
                pre = cur;
                cur = cur->next;
            }
    }
    struct ListNode *ret = dummy->next;
    free(dummy);
    return ret;
}

解法二通过哈希表优化了查找过程，在nums数组较大时性能提升显著。这是一个典型的空间换时间的优化策略。