Fusionner les listes triées

Aujourd'hui, nous examinons une autre tâche de liste chaînée.

Créez une fonction pour fusionner 2 listes chaînées triées. La liste résultante doit être une liste triée en utilisant les nœuds des 2 listes.

Pour cela, nous utiliserons l'implémentation de liste chaînée générique du post précédent qui peut être trouvée ici

func mergeSortedLists(ll1 LinkedList[int], ll2 LinkedList[int]) LinkedList[int] {
    result := LinkedList[int]{}

    p1 := ll1.Head
    p2 := ll2.Head
    rp := &Node[int]{} // dummy node as result head
    result.Head = rp
    for p1 != nil && p2 != nil {
        if p1.Data >= p2.Data {
            rp.Next = p2
            p2 = p2.Next
        } else {
            rp.Next = p1
            p1 = p1.Next
        }
        rp = rp.Next
    }
    if p1 != nil {
        rp.Next = p1
    }
    if p2 != nil {
        rp.Next = p2
    }
    result.Head = result.Head.Next
    return result
}

La logique est assez facile à suivre. Tout d’abord, nous configurons des pointeurs vers les têtes des 2 listes et la liste résultante. Puisque nous ne connaissons pas la « tête » de la liste résultante, nous créons un nœud factice comme espace réservé (nous le corrigerons plus tard). Nous créons également un nœud courant, rp, pour la liste de résultats.

Ensuite, nous parcourons les 2 listes. Nous avons un nœud actuel pour chaque liste. À chaque étape, nous regardons lequel des 2 nœuds actuels a la plus petite valeur et mettons ce nœud sur la liste des résultats. Déplacez ensuite le nœud actuel de cette liste (celui qui était plus petit) vers le nœud suivant de la liste. Nous devons également déplacer le nœud actuel du résultat vers l'endroit suivant.

Notre logique de boucle consiste simplement à continuer ainsi jusqu'à ce que nous atteignions la fin de l'une des listes. A ce stade, nous savons qu'il n'y a plus d'éléments à comparer pour l'une des listes ; ils sont déjà dans la liste des résultats. Ainsi, on peut alors simplement mettre les nœuds restants de l'autre liste à la fin du résultat, puisqu'on sait qu'ils sont déjà triés.

Comment feriez-vous cela différemment ? Pouvons-nous optimiser cela ? 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!