Merge Two Sorted Lists

Q: Quelle est la complexité temporelle de la fusion de deux listes triées ?

C'est O(L1 + L2) : chaque comparaison place un nœud, et aucun nœud n'est placé deux fois. Avec des objets nœuds, la fusion nécessite O(1) mémoire supplémentaire, puisqu'elle ne fait que modifier les liens. Avec les tableaux utilisés ici, le tableau de liens partagé nécessite O(L1 + L2) mémoire.

FacileListe chaînée Deux pointeurs

+10

Tu reçois deux listes simplement chaînées, chacune stockée dans deux tableaux de même longueur. Dans la première liste, le nœud i contient la valeur values1[i] et pointe vers le nœud next1[i]. La seconde liste fonctionne de la même manière avec next2 et values2. Dans les deux listes, -1 marque la fin de la liste et la tête est le nœud 0. Les nœuds ne sont pas stockés dans l’ordre de la liste : suis donc les liens.

Chaque liste est triée par ordre non décroissant le long de ses liens. Fusionne les deux listes en une seule liste triée et renvoie ses valeurs dans l’ordre.

Fonction

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: l’index du nœud vers lequel pointe chaque nœud de la première liste, ou -1 pour son dernier nœud
values1integer-array: la valeur contenue dans chaque nœud de la première liste
next2integer-array: l’index du nœud vers lequel pointe chaque nœud de la deuxième liste, ou -1 pour son dernier nœud
values2integer-array: la valeur détenue par chaque nœud de la deuxième liste
Renvoieinteger-array: les valeurs de la liste fusionnée, dans l’ordre

Contraintes

1 ≤ L1 ≤ 2000, où L1 est la longueur de next1 et de values1.
1 ≤ L2 ≤ 2000, où L2 est la longueur de next2 et de values2.
-1000 ≤ values1[i], values2[j] ≤ 1000
Chaque élément de next1 est -1 ou un indice de nœud de la première liste, et chaque élément de next2 est -1 ou un indice de nœud de la deuxième liste.
En partant du nœud 0, chaque liste visite chacun de ses nœuds exactement une fois, puis atteint -1. Il n’y a pas de cycle.
Le long de ses liens, chaque liste est triée par ordre non décroissant.

Exemples

Entrée: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Sortie: [1, 2, 3, 4, 6, 7, 9]
Explication: En suivant les liens, la première liste visite les nœuds 0, 2, 1 et lit 1, 4, 6 ; la seconde lit 2, 3, 7, 9. En prenant à chaque fois le plus petit élément en tête, on obtient 1, 2, 3, 4, 6, 7, 9.

Entrée: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Sortie: [-3, 0, 0, 5]
Explication: La première liste contient -3, 0, 5 et la seconde est la valeur unique 0. Les deux 0 restent dans le résultat, qui contient donc quatre valeurs.

Entrée: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Sortie: [1, 2, 3, 8, 10]
Explication: La deuxième liste affiche 1, 2, 3, tous plus petits que le 8 qui commence la première liste. La deuxième liste entière vient en premier, puis 8, 10.

Pour aller plus loin

Peux-tu fusionner k listes triées en O(N log k) temps, où N est le nombre total de nœuds ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Les deux listes sont triées, donc la plus petite valeur restante se trouve toujours au début de l'une d'elles. Comparez les deux premières valeurs, reliez la plus petite au résultat, puis avancez dans cette liste. Le tri des N = L1 + L2 valeurs fonctionne aussi, mais il ignore cet ordre et coûte O(N log N).

Place toutes les valeurs dans un seul tableau et trie-le

Intuition

La liste fusionnée est la version triée de toutes les valeurs N ; copiez donc les deux tableaux de valeurs dans un seul, puis triez-le. L’ordre des nœuds dans les tableaux n’a pas d’importance, car le tri place chaque valeur. Avec N ≤ 4000, cette solution est suffisamment rapide, mais un tri nécessite O(N log N) comparaisons, alors qu’une fusion en nécessite au plus N-1 et ne touche jamais à un lien, compétence évaluée par ce problème.

Algorithme

Copiez values1 et values2 dans un seul tableau.
Triez le tableau par ordre non décroissant.
Renvoyez-le.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

Insérez les nœuds derrière une tête factice

Intuition

Un pointeur désigne ici l’indice d’un nœud. Pour relier les nœuds des deux listes en une seule chaîne, attribuez-leur une numérotation commune : le nœud j de la liste 2 devient le nœud L1+j, et ses liens sont décalés de la même façon. Un nœud fictif, numéroté L1+L2, se trouve devant le résultat.

Gardez a et b sur le premier nœud non utilisé de chaque liste, et tail à la fin de la chaîne fusionnée. À chaque étape, reliez tail au plus petit des deux premiers nœuds, puis avancez ce pointeur et tail. Quand une liste est épuisée, le reste de l’autre est déjà trié et relié, donc une seule affectation suffit pour l’attacher. Dans le premier exemple, la liste 2 devient les nœuds 3 à 6. Après les nœuds 0, 3, 6, 2, 1, la liste 1 est vide et link[tail] = 4 attache 7, 9.

Chaque nœud est relié au plus une fois : temps O(N). Le tableau de liens partagé utilise une mémoire de O(N), contrairement aux objets nœuds, qui n’en nécessiteraient aucune.

Algorithme

Construis un tableau de liens : next1, puis next2 décalé de L1 (laisse -1 tel quel), puis -1 pour la sentinelle L1+L2. Construis les valeurs correspondantes.
Définis a = 0, b = L1 et tail sur la sentinelle.
Tant que ni a ni b n’est égal à -1, relie tail au plus petit (à a en cas d’égalité), avance ce pointeur et déplace tail dessus.
Relie tail à celui de a et b qui n’est pas égal à -1.
Parcours à partir de link[dummy] jusqu’à -1 et collecte les valeurs.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

Pièges et cas limites

Fusionner les tableaux dans l’ordre des indices. Les nœuds sont stockés dans le désordre, donc values1 n’est pas trié en lui-même : dans le premier exemple, il vaut [1, 6, 4]. Seul le parcours à partir du nœud 0 est trié.
Oublier les éléments restants. Quand une liste est épuisée, la boucle s’arrête, et supprimer le reste de l’autre liste fait perdre les plus grandes valeurs : 7, 9 dans le premier exemple.
Avancer le mauvais pointeur, ou les deux. Seule la liste dont vous avez pris le nœud avance.
Mélanger les deux numérotations. Le nœud 2 de la liste 2 n’est pas le nœud 2 de la liste 1. Décalez les indices et les liens de la liste 2 de L1, et laissez -1 tel quel.

Questions fréquentes3

Quelle est la complexité temporelle de la fusion de deux listes triées ?

C'est O(L1 + L2) : chaque comparaison place un nœud, et aucun nœud n'est placé deux fois. Avec des objets nœuds, la fusion nécessite O(1) mémoire supplémentaire, puisqu'elle ne fait que modifier les liens. Avec les tableaux utilisés ici, le tableau de liens partagé nécessite O(L1 + L2) mémoire.

Pourquoi utiliser un nœud factice lors de la fusion de listes chaînées ?

Sans cela, le premier nœud du résultat nécessite un code distinct, car il n’y a pas encore de queue à laquelle le relier. Le nœud factice est une tête de remplacement, ainsi le premier nœud est relié de la même manière que tous les autres. À la fin, tu renvoies le nœud suivant du nœud factice et le placeholder disparaît.

Faut-il fusionner deux listes triées de manière récursive ou itérative ?

La version récursive est courte : la tête la plus petite pointe vers la fusion de tout le reste. Mais elle utilise une trame de pile par nœud, si bien qu’une liste de quelques milliers de nœuds peut provoquer un dépassement de pile dans certains langages. La boucle itérative avec un pointeur de queue effectue le même travail avec un espace de pile constant.

def mergeTwoLists(next1, values1, next2, values2):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

Résultat attendu

[1, 2, 3, 4, 6, 7, 9]