Vérifiez si deux listes liées fusionnent. Si oui où?

Question

Cette question est peut-être ancienne, mais je ne pouvais pas penser à une réponse.

Disons qu'il existe deux listes de longueurs différentes, fusionnant en un point ; Comment savons-nous où se trouve le point de fusion?

Conditions:

1. Nous ne connaissons pas la longueur
2. Nous devrions analyser chaque liste une seule fois.

Answer 1

Ce qui suit est de loin le plus grand de tout ce que j'ai vu - O(N), pas de compteurs. Je l'ai eu lors d'une interview à un candidat à la S. N. à VisionMap.

Faire un interating pointeur comme ceci: il va de l'avant à chaque fois jusqu'à la fin, et puis saute au début de la face de la liste, et ainsi de suite. Créez deux de ces, pointant à deux têtes. L'avance chacun des pointeurs par 1 à chaque fois, jusqu'à ce qu'ils rencontrent. Ce sera le cas après une ou deux passes.

J'utilise encore cette question dans les entretiens - mais pour voir combien de temps il faut quelqu'un pour comprendre pourquoi cette solution fonctionne.

Answer 2

Pavel réponse nécessite une modification des listes ainsi que d' une itération à chaque liste à deux reprises.

Voici une solution que seulement nécessite une itération à chaque liste en deux fois (la première fois pour le calcul de leur longueur; si la longueur est donné seulement à itérer une fois).

L'idée est d'ignorer le départ des entrées de la liste la plus longue (de fusion point ne peut pas être là), de sorte que les deux pointeurs sont à égale distance de la fin de la liste. Puis déplacez-les transmet jusqu'à ce qu'ils fusionnent.

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

C'est asymptotiquement la même (temps linéaire) comme mon autre réponse, mais probablement moins constantes, donc c'est probablement plus rapide. Mais je pense que ma réponse est plus frais.

Answer 3

Si

• par une modification non autorisée", il a été signifié "vous pouvez changer, mais à la fin, ils devraient être restaurée", et
• nous avons pu parcourir les listes exactement deux fois

l'algorithme suivant serait la solution.

Tout d'abord, les chiffres. Supposons le premier de la liste est de longueur a+c et le second est de longueur b+coù c est la longueur de la "queue" (après la mergepoint). Nous allons désigner comme suit:

x = a+c
y = b+c

Puisque nous ne connaissons pas la longueur, nous allons calculer l' x et y sans des itérations supplémentaires; vous verrez comment.

Ensuite, nous itération de chaque liste et pour renverser la vapeur lors de l'itération! Si les deux itérateurs atteindre le point de fusion dans le même temps, alors nous trouver par simple comparaison. Sinon, un pointeur d'atteindre le point de fusion avant l'autre.

Après cela, quand les autres itérateur atteint le point de fusion, il ne procédera pas à la commune de la queue. Au lieu de cela va revenir à l'ancien début de la liste qui avaient atteint la fusion-point avant! Donc, avant qu'il n'atteigne la fin de la modification de la liste (c'est à dire l'ex-début de la liste), il prendra a+b+1 d'itérations total. Appelons - z+1.

Le pointeur atteint la fusion point d'abord, permet de garder l'itération, jusqu'à atteindre la fin de la liste. Le nombre d'itérations, il doit être calculée et est égale à x.

Ensuite, ce pointeur itère arrière et annule les listes de nouveau. Mais maintenant, il ne sera pas revenir au début de la liste qu'il a commencé à partir de! Au lieu de cela, il va aller au début de la liste autres! Le nombre d'itérations, il doit être calculé et égale à y.

Donc, nous savons que l'un des numéros suivants:

x = a+c
y = b+c
z = a+b

À partir de laquelle nous déterminons que

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

Ce qui résout le problème.

Answer 4

Eh bien, si vous savez qu'ils vont fusionner:

Dites que vous commencez par:

 A-->B-->C
        |
        V
1-->2-->3-->4-->5
 

1) Parcourez la première liste en réglant chaque pointeur sur NULL.

Maintenant vous avez:

 A   B   C

1-->2-->3   4   5
 

2) Maintenant, parcourez la deuxième liste et attendez que NULL apparaisse, c’est votre point de fusion.

Si vous ne pouvez pas être sûr qu'ils fusionnent, vous pouvez utiliser une valeur sentinelle pour la valeur du pointeur, mais ce n'est pas aussi élégant.

Answer 5

Si nous pouvions itérer des listes exactement deux fois, je pourrais fournir une méthode pour déterminer le point de fusion:

• itérer les deux listes et calculer les longueurs A et B
• calculer la différence de longueur C = | AB |;
• commencer à itérer les deux listes simultanément, mais faire des étapes C supplémentaires sur la liste, ce qui était plus important
• ces deux pointeurs se rencontreront dans le point de fusion