從數組中存在的鍊錶中刪除節點

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中文網其他相關文章！