从数组中存在的链表中删除节点-php教程-PHP中文网

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

王林

发布： 2024-09-07 16:30:32

原创

849 人浏览过

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 中。

提示：

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

解决方案：

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

方法：

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

步骤：

将 nums 转换为哈希集以进行 O(1) 查找。
使用两个指针遍历链表：一个用于当前节点，一个用于前一个节点，以帮助高效删除节点。
对于每个节点，检查该值是否在哈希集中。如果是，则更新前一个节点的 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
?>

登录后复制

解释：

removeElements($head, $nums):
- 我们首先将 nums 转换为哈希集 ($numSet = array_flip($nums);) 以进行快速查找。
- 创建一个虚拟节点并将其链接到列表的头部。这有助于简化边缘情况，例如删除头节点。
- 上一个指针跟踪当前节点之前的节点，允许我们通过在列表中跳过当前节点来删除它。
- 对于每个节点，我们检查它的值是否在 numSet 中。如果是这样，我们通过调整 prev->next 指针来跳过当前节点来删除它。
边缘情况：
- 如果需要删除头节点，虚拟节点可确保可以干净地删除头节点并仍然返回正确的列表。
- 处理需要删除多个连续节点的情况。
复杂性：
- 时间复杂度：O(n)，其中n是链表中的节点数。我们访问每个节点一次。将 nums 转换为集合需要 O(m)，其中 m 是 nums 的大小。
- 空间复杂度：O(m)，用于存储数字集。