配列内に存在するリンクされたリストからノードを削除-PHPチュートリアル-php.cn

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

王林

リリース： 2024-09-07 16:30:32

オリジナル

805 人が閲覧しました

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 つ存在するように生成されます。

ヒント:

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

解決策:

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

アプローチ：

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

手順:

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

このソリューションを 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);) に変換します。
- ダミーノードが作成され、リストの先頭にリンクされます。これは、ヘッドノードの削除などの特殊なケースを簡素化するのに役立ちます。
- prev ポインターは現在のノードの前のノードを追跡するため、リスト内で現在のノードをスキップして削除できます。
- 各ノードについて、その値が numSet にあるかどうかを確認します。その場合、現在のノードをスキップするように prev->next ポインタを調整して削除します。
エッジケース:
- ヘッドノードを削除する必要がある場合、ダミーノードはヘッドを確実に削除し、正しいリストを返すことができることを保証します。
- 複数の連続したノードを削除する必要があるケースを処理します。
複雑さ:
- 時間計算量: O(n)、n はリンクリスト内のノードの数です。各ノードを 1 回ずつ訪問します。 nums を集合に変換するには O(m) がかかります。ここで、m は nums のサイズです。
- 空間複雑度: 数値セットを保存するための O(m)。