配列内に存在するリンクされたリストからノードを削除

3217。配列内に存在するリンクされたリストからノードを削除

難易度: 中

トピック: 配列、ハッシュ テーブル、リンク リスト

整数 num の配列とリンク リストの先頭が与えられます。 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 つ存在するように生成されます。

ヒント:

1. nums のすべての要素を Set に追加します。
2. リストをスキャンして、セットをチェックして現在の要素を削除する必要があるかどうかを確認します。

解決策:

リンクされたリストをたどって、配列 nums に値が存在するノードをすべて削除する必要があります。

アプローチ：

1. 高速検索用のハッシュ セット: nums に値が存在するかどうかを効率的にチェックする必要があるため、nums をハッシュ セットに変換します。これにより、各値の O(1) ルックアップが可能になります。
2. リンクされたリストを反復処理します: リンクされたリストを反復処理し、ハッシュ セットに値が存在するノードを削除します。
3. ポインター操作: 反復中に、nums 配列の値と一致するノードを「スキップ」するようにポインターを調整します。

手順:

1. O(1) ルックアップ用に nums をハッシュ セットに変換します。
2. ノードを効率的に削除できるように、2 つのポインターを使用してリンク リストをトラバースします。1 つは現在のノード用、もう 1 つは前のノード用です。
3. 各ノードについて、値がハッシュ セットに含まれているかどうかを確認します。存在する場合は、前のノードの次を更新して、現在のノードをスキップします。

このソリューションを 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);) に変換します。
   • ダミーノードが作成され、リストの先頭にリンクされます。これは、ヘッド ノードの削除などの特殊なケースを簡素化するのに役立ちます。
   • prev ポインターは現在のノードの前のノードを追跡するため、リスト内で現在のノードをスキップして削除できます。
   • 各ノードについて、その値が numSet にあるかどうかを確認します。その場合、現在のノードをスキップするように prev->next ポインタを調整して削除します。

2. エッジケース:

   • ヘッド ノードを削除する必要がある場合、ダミー ノードはヘッドを確実に削除し、正しいリストを返すことができることを保証します。
   • 複数の連続したノードを削除する必要があるケースを処理します。

3. 複雑さ:

   • 時間計算量: O(n)、n はリンク リスト内のノードの数です。各ノードを 1 回ずつ訪問します。 nums を集合に変換するには O(m) がかかります。ここで、m は nums のサイズです。
   • 空間複雑度: 数値セットを保存するための O(m)。

チュートリアルの例:

入力 nums = [1, 2, 3] および head = [1, 2, 3, 4, 5] の場合、アルゴリズムは次のようになります:

• ノード 1 から開始し、nums に 1 が含まれているかどうかを確認し、それを削除します。
• ノード 2 に移動し、nums に 2 が含まれているかどうかを確認して、ノード 2 を削除します。
• ノード 3 に移動し、nums に 3 が含まれているかどうかを確認して、ノード 3 を削除します。
• ノード 4 と 5 に移動します。これらは nums に含まれていないため、リストに残ります。

結果のリンク リストは [4, 5] です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が配列内に存在するリンクされたリストからノードを削除の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。