Intersection of Two Linked Lists

+10

Deux listes simplement chaînées se trouvent dans un même ensemble de nœuds. Le nœud i pointe vers le nœud next[i], et -1 marque la fin d’une liste. La liste A commence au nœud headA et la liste B au nœud headB. Les nœuds ne sont pas stockés dans un ordre particulier : suivez donc les liens.

Les deux listes peuvent se rejoindre : à partir d’un certain nœud, elles continuent à travers les mêmes nœuds jusqu’à la fin. Renvoyez l’indice du premier nœud commun aux deux listes, ou -1 si elles n’ont aucun nœud en commun.

Fonction

getIntersectionNode(next: integer-array, headA: integer, headB: integer) → integer

nextinteger-array: l’index du nœud vers lequel chaque nœud pointe, ou -1 pour le dernier nœud d’une liste
headAinteger: le premier nœud de la liste A
headBinteger: le premier nœud de la liste B
Renvoieinteger: le premier nœud que les deux listes ont en commun, ou -1

Contraintes

2 ≤ n ≤ 10⁴, où n est la longueur de next.
Chaque next[i] vaut -1 ou un indice de nœud compris entre 0 et n-1.
0 ≤ headA, headB ≤ n-1 et headA ≠ headB.
Les deux listes se terminent par -1 sans visiter un nœud deux fois. Il n’y a pas de cycle.
Chaque nœud se trouve dans la liste A, dans la liste B ou dans les deux.

Exemples

Entrée: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Sortie: 1
Explication: A parcourt 3, 5, 1, 4, 0 et B parcourt 2, 1, 4, 0. À partir du nœud 1, ils partagent tous les nœuds, et aucun nœud antérieur de A ne se trouve sur le parcours de B ; la réponse est donc 1.

Entrée: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Sortie: -1
Explication: La liste A est 0, 2, 4 et la liste B est 1, 3. Elles se terminent toutes deux à -1 sans atteindre de nœud commun, donc la réponse est -1.

Entrée: next = [3, 2, 0, -1]headA = 1headB = 0
Sortie: 0
Explication: La liste A est 1, 2, 0, 3 et la liste B est 0, 3. La liste B est la queue de la liste A, donc le premier nœud commun est headB lui-même, le nœud 0.

Pour aller plus loin

Peux-tu trouver le nœud en O(m + k) temps avec O(1) mémoire supplémentaire ?

Indices

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

0 sur 3 ouverts

Solution

Un nœud a un seul next, donc deux listes qui se rejoignent ne se séparent plus. Elles forment un Y : deux débuts distincts reliés à une queue commune, et la réponse est le point de jonction. Les débuts peuvent être de longueurs différentes, donc avancer dans les deux listes simultanément fait manquer le point de jonction. Ci-dessous, m et k sont les longueurs de A et B.

Vérifier chaque nœud de A par rapport à tous les nœuds de B

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Un pointeur est un indice de nœud, et avancer revient à écrire node = next[node]. Pour chaque nœud a de A, dans l’ordre, parcourez tous les nœuds de B et comparez chacun à a. Le premier a qui correspond est la réponse, car tous les nœuds précédents de A ont déjà échoué. B est parcourue à nouveau pour chaque nœud de A : avec 5000 nœuds dans chaque liste et aucun nœud commun, cela représente 2.5 × 10^7 comparaisons.

Algorithme

Définissez a = headA.
Tant que a n’est pas -1, parcourez b depuis headB jusqu’à -1.
Si b == a à un moment donné, renvoyez a.
Sinon, faites avancer a = next[a] et recommencez.
Si la liste A est épuisée, renvoyez -1.

def getIntersectionNode(next, headA, headB):
    a = headA
    while a != -1:
        # Is node a also on list B? Walk all of B to find out.
        b = headB
        while b != -1:
            if a == b:
                return a
            b = next[b]
        a = next[a]
    return -1

Marquer les nœuds de la liste B

Intuition

Répondez une fois pour chaque nœud à la question « ce nœud est-il sur B ? » : parcourez B et marquez chaque nœud dans un tableau booléen de taille n. Les index des nœuds sont de petits entiers, donc un tableau fait l’affaire à la place d’un ensemble de hachage. Parcourez ensuite A à partir de sa tête. Le premier nœud marqué est présent dans les deux listes, et c’est le premier de ce type puisque vous parcourez A dans l’ordre. Dans le premier exemple, B marque 2, 1, 4, 0, et le parcours de A passe par 3 et 5 avant de s’arrêter sur 1. Chaque liste est parcourue une seule fois, donc le temps d’exécution est de O(m + k), au prix de n marques.

Algorithme

Crée onB, un tableau de n booléens initialisés à false.
Parcours la liste B à partir de headB et définis onB[node] = true pour chaque nœud.
Parcours la liste A à partir de headA. Renvoie le premier nœud pour lequel onB[node] est true.
Si la liste A se termine, renvoie -1.

def getIntersectionNode(next, headA, headB):
    # Mark every node of list B.
    on_b = [False] * len(next)
    node = headB
    while node != -1:
        on_b[node] = True
        node = next[node]
    # The first marked node on list A is the meeting point.
    node = headA
    while node != -1:
        if on_b[node]:
            return node
        node = next[node]
    return -1

Deux pointeurs qui changent de liste

Intuition

Découpe chaque liste au point de jonction : A comporte x nœuds privés, puis les c nœuds partagés, et B comporte y nœuds privés, puis les mêmes c nœuds. Le pointeur a parcourt A, passe sur -1, puis repart de headB, et atteint le point de jonction pour la deuxième fois après x + c + 1 + y déplacements. Le pointeur b parcourt B, puis A, et arrive après y + c + 1 + x déplacements. Les totaux sont égaux. Dans le premier exemple, x = 2, y = 1 et c = 3, et les deux pointeurs se trouvent sur le nœud 1 après sept déplacements.

Sans queue partagée, les deux pointeurs se trouvent sur -1 après m + 1 + k déplacements (après m lorsque m = k), et la boucle renvoie -1. Cet arrêt commun explique pourquoi chaque pointeur passe sur -1 avant de changer de liste. Chaque pointeur se déplace au plus m + k + 1 fois, avec deux index en mémoire.

Algorithme

Définis a = headA et b = headB.
Tant que a != b : déplace a vers headB s’il vaut -1, sinon vers next[a].
Au même tour, déplace b vers headA s’il vaut -1, sinon vers next[b].
Quand la boucle se termine, renvoie a. C’est le premier nœud commun, ou -1.

def getIntersectionNode(next, headA, headB):
    a, b = headA, headB
    # Each pointer walks its own list, then the other one. Both cover
    # the same number of nodes, so they reach the meeting node together,
    # or reach -1 together when there is none.
    while a != b:
        a = headB if a == -1 else next[a]
        b = headA if b == -1 else next[b]
    return a

Pièges et cas limites

Passer directement du dernier nœud à l’autre tête, en ignorant l’arrêt sur -1. Lorsque les listes n’ont aucun élément en commun, les pointeurs ne contiennent jamais la même valeur et la boucle s’exécute indéfiniment.
Redémarrer un pointeur à sa propre tête. Chaque pointeur parcourt alors sa propre liste en boucle, et ils ne se rencontrent que lorsque leurs tours s’alignent, ce qui peut nécessiter jusqu’à (m + 1)·(k + 1) déplacements.
Considérer l’ordre du tableau comme l’ordre de la liste. Le nœud 0 est une tête uniquement si headA ou headB l’indique, et les éléments voisins du tableau ne sont pas des voisins dans une liste.
En Lua et R, ne pas oublier que les tableaux commencent à 1. Garder les indices des nœuds à base 0 et lire next[node + 1].

Questions fréquentes3

Comment trouver le point d’intersection de deux listes chaînées sans mémoire supplémentaire ?

Faites avancer deux pointeurs. Chacun parcourt sa propre liste puis, après avoir dépassé la fin, repart de la tête de l’autre liste. Ils parcourent la même distance totale et atteignent donc le premier nœud partagé au même moment, ou arrivent ensemble à la fin s’il n’y en a pas.

Peux-tu trouver l’intersection en comparant les longueurs des listes ?

Oui. Comptez les nœuds des deux listes, avancez le pointeur de la liste la plus longue du nombre de positions correspondant à la différence, puis avancez les deux d’un pas à la fois jusqu’à ce qu’ils soient égaux. Cela prend également O(m + k) et utilise O(1) mémoire ; la méthode de commutation obtient le même alignement sans les deux parcours de comptage.

Quelle est la complexité temporelle pour trouver l’intersection de deux listes chaînées ?

Les deux méthodes utilisant des pointeurs et la longueur s’exécutent en O(m + k) avec une mémoire supplémentaire de O(1). Mémoriser une liste dans un ensemble ou un tableau de marquage est également linéaire, mais nécessite de la mémoire pour cette liste. Comparer chaque paire de nœuds prend O(m·k).

def getIntersectionNode(next, headA, headB):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

next = [-1, 4, 1, 5, 0, 1]
headA = 3
headB = 2

Résultat attendu

Intersection of Two Linked Lists

Fonction

Contraintes

Exemples

Indices

Solution

Vérifier chaque nœud de A par rapport à tous les nœuds de B

Marquer les nœuds de la liste B

Deux pointeurs qui changent de liste

Pièges et cas limites

Questions fréquentes3

Problèmes similaires