Supprimer le Nième de la fin de la liste chaînée

Dans cet article, j'explore un autre algorithme de liste chaînée. Celui-ci est un peu plus difficile.

Créez une fonction pour supprimer le nième nœud de la fin d'une liste chaînée.

Cela vient d'un problème de leetcode. Comme dans le problème du leetcode, 'n' est basé sur un et peut aller de 1 à la longueur de la liste.

func (ll *LinkedList[T]) RemoveNthFromEnd(n int) *Node[T] {
    if n == 0 {
        return nil
    }
    fast := ll.Head // this moves to the end
    slow := ll.Head // this should be one behind the nth from end

    for count := 0; count < n; count++ {
        if fast == nil { // list is too short
            return nil
        }
        fast = fast.Next
    }
    if fast == nil { // special case, removing head
        res := ll.Head
        ll.Head = ll.Head.Next
        return res
    }
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }
    res := slow.Next
    slow.Next = slow.Next.Next
    return res
}

La clé pour cela est d'utiliser des pointeurs doubles. Nous commençons par initialiser un pointeur rapide et un pointeur lent vers la tête de liste.

Ensuite, nous avançons le pointeur rapide n nœuds. De cette façon, le pointeur lent se trouve désormais « n » derrière le pointeur rapide. Maintenant, nous pouvons déplacer les deux pointeurs en pas de verrouillage jusqu'à ce que fast soit à la fin.

Nous pouvons ensuite supprimer le nième avant-dernier nœud et le renvoyer.

Y a-t-il une meilleure façon ? Faites-le-moi savoir dans les commentaires.

Merci !

Le code de cet article et de tous les articles de cette série peut être trouvé ici

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!