菜单
文章

3217. 从链表中移除在数组中存在的节点

beautifulremi

beautifulremi

• 阅读本文需 5 分钟

题目

给你一个整数数组 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 数组来查找。

  • 性能分析：如果链表有 $N$ 个节点，nums 数组有 $M$ 个元素。这个操作的时间复杂度将是 $O(N \times M)$。
  • 根据提示：$N$ 和 $M$ 都可以高达 $10^5$。$O(10^5 \times 10^5)$ 是一个天文数字，程序一定会超时。
  • 对策：空间换时间（使用哈希表）我们需要一个 $O(1)$（即时）的查找方法。哈希表（在 Go 中是 map，在 C++ 中是 unordered_set）是完美的选择。
    1. 预处理：首先遍历 nums 数组（$O(M)$ 时间），将所有要删除的数字存入一个哈希表（numSet）。
    2. 查询：在遍历链表时，检查节点值 val 是否在哈希表中（numSet[val]），这个操作的平均时间复杂度是 $O(1)$。
  • 本题的“特定优化”：提示中说 1 <= Node.val <= 10^5。这意味着我们可以用一个数组来模拟哈希表！
    1. 创建一个大小为 100001 的布尔数组：toDelete[100001]bool。
    2. 遍历 nums，toDelete[x] = true。
    3. 检查时，直接看 toDelete[node.Val] 是否为 true 即可。

总时间复杂度：$O(M)$ 预处理 + $O(N)$ 遍历链表 = $O(N + M)$。这非常快。

删除节点

在单链表中，要删除一个节点 B（在 A -> B -> C 中），你必须拥有对它前一个节点 A 的访问权，然后执行 A.Next = C (即 A.Next = B.Next)。

  • 问题：如果你只用一个指针 cur 遍历，当 cur 指向 B 时，你已经“错过” A 了，无法执行删除。
  • 对策1（双指针）：使用 prev 和 cur 两个指针。prev 始终指向 cur 的前一个。
  • 问题：如果第一个节点（head）就需要被删除怎么办？它的 prev 是 nil，prev.Next 会导致程序崩溃。你需要写很多额外的 if head == ... 来处理边界情况。
  • 对策2（最佳实践：哨兵节点 Dummy Node） 这是解决链表删除（尤其是头节点删除）的万能技巧。
    1. 创建一个全新的、临时的“哨兵”节点 dummy。
    2. 让 dummy.Next 指向你真正的 head：dummy -> head -> ...
    3. 现在，head 节点也变成了一个有“前一个”节点（dummy）的普通节点。
    4. 我们从 dummy 节点开始进行“前一个”指针的遍历。

具体代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func modifiedList(nums []int, head *ListNode) *ListNode {
    // 创建一个哨兵（dummy）节点，它的 Next 指向真正的 head
    // 这样可以统一处理删除头节点的情况
    dummy := &ListNode{Next: head}
    
    // cur 指针用于遍历，从哨兵节点开始
    cur := dummy
    
    // 使用一个布尔数组作为哈希表（集合），快速查找 nums 里的数
    // 假设题目约束了节点值在 0 到 100000 之间
    cnt := [100001]bool{}
    for _, x := range nums {
        cnt[x] = true
    }

    // 遍历链表
    // 我们总是检查 cur 的 *下一个* 节点 (cur.Next)
    for cur.Next != nil {
        // 取出下一个节点的值
        x := cur.Next.Val
        
        // 检查这个值是否在 nums 数组中（即 cnt[x] 是否为 true）
        if cnt[x] {
            // 是：需要删除 cur.Next 节点
            // 通过让 cur.Next "跳过" 下一个节点，指向下下个节点来实现删除
            cur.Next = cur.Next.Next
        } else {
            // 否：保留 cur.Next 节点
            // 将 cur 指针正常后移
            cur = cur.Next
        }
    }
    
    // 返回哨兵节点的下一个，这才是修改后链表的真正头节点
    return dummy.Next
}
分享