从数组中存在的链表中删除节点

3217。从数组中存在的链表中删除节点

难度：中等

主题：数组、哈希表、链表

给你一个整数数组 nums 和一个链表的头。从链表中删除所有具有 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 5
• 1 5
• nums 中的所有元素都是唯一的。
• 给定列表中的节点数量在 [1, 10⁵] 范围内。
• 1 5
• 生成输入，使得链表中至少有一个节点的值不存在于 nums 中。

提示：

1. 将 nums 的所有元素添加到 Set 中。
2. 扫描列表，通过检查Set来检查当前元素是否应该被删除。

解决方案：

我们需要遍历链表并删除数组 nums 中存在值的所有节点。

方法：

1. 用于快速查找的哈希集：由于检查 nums 中是否存在值需要高效，因此我们将 nums 转换为哈希集。这允许 O(1) 查找每个值。
2. 迭代链表：我们将迭代链表并删除其值存在于哈希集中的节点。
3. 指针操作：迭代时，我们将调整指针以“跳过”与 nums 数组中的值匹配的节点。

步骤：

1. 将 nums 转换为哈希集以进行 O(1) 查找。
2. 使用两个指针遍历链表：一个用于当前节点，一个用于前一个节点，以帮助高效删除节点。
3. 对于每个节点，检查该值是否在哈希集中。如果是，则更新前一个节点的 next 以跳过当前节点。

让我们用 PHP 实现这个解决方案：3217。从数组中存在的链表中删除节点

<?php // Definition for a singly-linked list node.
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {

    /**
     * @param Integer[] $nums
     * @param ListNode $head
     * @return ListNode
     */
    function removeElements($head, $nums) {
        ...
        ...
        ...
        /**
         * go to ./solution.php
         */
    }
}

// Example usage:

// Linked List: 1 -> 2 -> 3 -> 4 -> 5
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

// Array nums: [1, 2, 3]
$nums = [1, 2, 3];

$solution = new Solution();
$result = $solution->removeElements($head, $nums);

// Function to print the linked list
function printList($node) {
    while ($node !== null) {
        echo $node->val . " ";
        $node = $node->next;
    }
}

// Print the resulting linked list
printList($result); // Output: 4 5
?>

解释：

1. removeElements($head, $nums):

   • 我们首先将 nums 转换为哈希集 ($numSet = array_flip($nums);) 以进行快速查找。
   • 创建一个虚拟节点并将其链接到列表的头部。这有助于简化边缘情况，例如删除头节点。
   • 上一个指针跟踪当前节点之前的节点，允许我们通过在列表中跳过当前节点来删除它。
   • 对于每个节点，我们检查它的值是否在 numSet 中。如果是这样，我们通过调整 prev->next 指针来跳过当前节点来删除它。

2. 边缘情况：

   • 如果需要删除头节点，虚拟节点可确保可以干净地删除头节点并仍然返回正确的列表。
   • 处理需要删除多个连续节点的情况。

3. 复杂性：

   • 时间复杂度：O(n)，其中n是链表中的节点数。我们访问每个节点一次。将 nums 转换为集合需要 O(m)，其中 m 是 nums 的大小。
   • 空间复杂度：O(m)，用于存储数字集。

演练示例：

对于输入 nums = [1, 2, 3] 和 head = [1, 2, 3, 4, 5]，算法将：

• 从节点1开始，检查nums中是否有1，然后将其删除。
• 移动到节点 2，检查 2 是否在 nums 中，然后将其删除。
• 移动到节点 3，检查 3 是否在 nums 中，然后将其删除。
• 移动到节点 4 和 5，它们不在 nums 中，因此它们保留在列表中。

生成的链表是 [4, 5]。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是从数组中存在的链表中删除节点的详细内容。更多信息请关注PHP中文网其他相关文章！