Medium

题目描述

给你一个整数数组 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 <= 10^5
  • 1 <= nums[i] <= 10^5
  • nums 中的所有元素都是唯一的
  • 给定链表中节点数量的范围是 [1, 10^5]
  • 1 <= Node.val <= 10^5
  • 输入保证链表中至少有一个节点的值不在 nums 中

提示：

  • 将 nums 的所有元素添加到一个集合中
  • 扫描链表，通过检查集合来确定当前元素是否应该被删除

解题思路

这道题要求从链表中删除所有在数组中出现的节点。我们可以采用哈希表优化的方法来解决。

核心思路：

  1. 预处理数组：将数组 nums 转换为哈希集合，这样查找某个值是否存在的时间复杂度就是 O(1)。

  2. 处理头节点：由于头节点可能需要被删除，我们需要先处理头节点，找到第一个不需要删除的节点作为新的头节点。

  3. 遍历链表：从新的头节点开始遍历，对于每个节点，检查其下一个节点是否需要删除。如果需要删除，就跳过该节点；否则继续向前移动。

算法步骤：

  • 使用哈希集合存储所有需要删除的值
  • 找到新的头节点（第一个不在删除列表中的节点）
  • 使用双指针技术，current 指向当前节点，检查 current.next 是否需要删除
  • 如果需要删除，直接修改指针跳过该节点；否则移动到下一个节点

这种方法避免了复杂的边界情况处理，代码简洁且易于理解。时间复杂度为 O(n + m)，其中 n 是链表长度，m 是数组长度。

代码实现

class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        unordered_set<int> toDelete(nums.begin(), nums.end());
        
        // 找到新的头节点
        while (head && toDelete.count(head->val)) {
            head = head->next;
        }
        
        // 如果链表为空，直接返回
        if (!head) return nullptr;
        
        // 删除中间和尾部的节点
        ListNode* current = head;
        while (current->next) {
            if (toDelete.count(current->next->val)) {
                current->next = current->next->next;
            } else {
                current = current->next;
            }
        }
        
        return head;
    }
};

class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        to_delete = set(nums)
        
        # 找到新的头节点
        while head and head.val in to_delete:
            head = head.next
        
        # 如果链表为空，直接返回
        if not head:
            return None
        
        # 删除中间和尾部的节点
        current = head
        while current.next:
            if current.next.val in to_delete:
                current.next = current.next.next
            else:
                current = current.next
        
        return head

public class Solution {
    public ListNode ModifiedList(int[] nums, ListNode head) {
        HashSet<int> toDelete = new HashSet<int>(nums);
        
        // 找到新的头节点
        while (head != null && toDelete.Contains(head.val)) {
            head = head.next;
        }
        
        // 如果链表为空，直接返回
        if (head == null) return null;
        
        // 删除中间和尾部的节点
        ListNode current = head;
        while (current.next != null) {
            if (toDelete.Contains(current.next.val)) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        
        return head;
    }
}

var modifiedList = function(nums, head) {
    const toDelete = new Set(nums);
    
    // 找到新的头节点
    while (head && toDelete.has(head.val)) {
        head = head.next;
    }
    
    // 如果链表为空，直接返回
    if (!head) return null;
    
    // 删除中间和尾部的节点
    let current = head;
    while (current.next) {
        if (toDelete.has(current.next.val)) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n + m)n 是链表长度，m 是数组长度。创建哈希集合需要 O(m)，遍历链表需要 O(n)
空间复杂度O(m)哈希集合存储数组中的所有元素，需要 O(m) 额外空间

相关题目