Supprimer les nœuds de la liste liée présente dans le tableau

3217. Supprimer les nœuds de la liste liée présente dans le tableau

Difficulté :Moyen

Sujets : Tableau, table de hachage, liste chaînée

Vous recevez un tableau de nombres entiers et le début d'une liste chaînée. Renvoie l'en-tête de la liste chaînée modifiée après avoir supprimé tous les nœuds de la liste chaînée qui ont une valeur qui existe en nombres.

Exemple 1 :

• Entrée : nums = [1,2,3], tête = [1,2,3,4,5]
• Sortie : [4,5]
• Explication : Supprimez les nœuds avec les valeurs 1, 2 et 3.

Exemple 2 :

• Entrée : Entrée : nums = [1], head = [1,2,1,2,1,2]
• Sortie : [2,2,2]
• Explication : Supprimez les nœuds de valeur 1.

Exemple 3 :

• Entrée : nums = [5], head = [1,2,3,4]
• Sortie : [1,2,3,4] Aucun nœud n'a la valeur 5.

Contraintes :

• 1 5
• 1 5
• Tous les éléments numériques sont uniques.
• Le nombre de nœuds dans la liste donnée est compris entre [1, 10⁵].
• 1 5
• L'entrée est générée de telle sorte qu'il y ait au moins un nœud dans la liste chaînée qui a une valeur non présente en chiffres.

Indice :

1. Ajoutez tous les éléments de nums dans un ensemble.
2. Scannez la liste pour vérifier si l'élément actuel doit être supprimé en cochant l'ensemble.

Solution :

Nous devons parcourir la liste chaînée et supprimer tous les nœuds qui ont une valeur présente dans le tableau nums.

Approche:

1. Jeu de hachage pour une recherche rapide : Puisque vérifier si une valeur existe en nombres doit être efficace, nous convertirons les nombres en un jeu de hachage. Cela permet la recherche O(1) pour chaque valeur.
2. Parcourir la liste chaînée : Nous allons parcourir la liste chaînée et supprimer les nœuds dont les valeurs sont présentes dans l'ensemble de hachage.
3. Manipulation du pointeur : lors de l'itération, nous ajusterons les pointeurs pour "ignorer" les nœuds qui correspondent aux valeurs du tableau nums.

Mesures:

1. Convertissez les nombres en un jeu de hachage pour la recherche O(1).
2. Parcourez la liste chaînée avec deux pointeurs : un pour le nœud actuel et un pour le nœud précédent pour aider à supprimer efficacement les nœuds.
3. Pour chaque nœud, vérifiez si la valeur est dans le jeu de hachage. Si tel est le cas, mettez à jour le prochain nœud précédent pour ignorer le nœud actuel.

Implémentons cette solution en PHP : 3217. Supprimer les nœuds de la liste liée présents dans le tableau

<?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
?>

Explication:

1. removeElements($head, $nums) :

   • Nous convertissons d'abord les nombres en un jeu de hachage ($numSet = array_flip($nums);) pour des recherches rapides.
   • Un nœud factice est créé et lié à la tête de liste. Cela permet de simplifier les cas extrêmes, comme la suppression du nœud principal.
   • Le pointeur précédent suit le nœud avant celui actuel, nous permettant de supprimer le nœud actuel en l'ignorant dans la liste.
   • Pour chaque nœud, on vérifie si sa valeur est dans numSet. Si tel est le cas, nous le supprimons en ajustant le pointeur prev->next pour ignorer le nœud actuel.

2. Cas Edge :

   • Si le nœud principal doit être supprimé, le nœud factice garantit que la tête peut être retirée proprement tout en renvoyant la liste correcte.
   • Gère les cas où plusieurs nœuds consécutifs doivent être supprimés.

3. Complexité :

   • Complexité temporelle : O(n), où n est le nombre de nœuds dans la liste chaînée. Nous visitons chaque nœud une fois. La conversion de nombres en un ensemble prend O(m), où m est la taille des nombres.
   • Complexité spatiale : O(m) pour stocker l'ensemble de nombres.

Exemple de procédure pas à pas :

Pour les nombres d'entrée = [1, 2, 3] et head = [1, 2, 3, 4, 5], l'algorithme :

• Commencez au nœud 1, vérifiez si 1 est en chiffres et supprimez-le.
• Déplacez-vous vers le nœud 2, vérifiez si 2 est en chiffres et supprimez-le.
• Déplacez-vous vers le nœud 3, vérifiez si 3 est en chiffres et supprimez-le.
• Déplacez-vous vers les nœuds 4 et 5, qui ne sont pas en chiffres, ils restent donc dans la liste.

La liste chaînée résultante est [4, 5].

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!