Vérifier si deux listes de fusion. Si oui, où?

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+c, où 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 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, lorsque 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 fera a+b+1 itérations total. Appelons ça de la 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.

Puis, 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

Qui résout le problème.

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

Voici une solution qui 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.

Si l'on peut itérer les listes exactement deux fois, que je peux fournir la méthode pour déterminer le point de fusion:

• itérer les deux listes et de calculer les longueurs A et B
• calculer la différence de longueurs de C = |A-B|;
• commencer à parcourir les deux listes en même temps, mais faire des C suit sur la liste qui a été de plus de
• ce deux pointeurs rencontrer les uns les autres dans la fusion point

Cela a sans doute viole la "analyser chaque liste qu'une seule fois" état, mais de mettre en place le la tortue et le lièvre de l'algorithme (utilisé pour trouver le point de fusion et la longueur du cycle de cyclique liste) si vous commencez à partir d'Une Liste, et lorsque vous atteignez la valeur NULL à la fin vous prétendez que c'est un pointeur vers le début de la liste B, créant l'apparence d'une reprise cyclique de la liste. L'algorithme ne puis vous dire exactement comment loin en bas de la Liste A de la fusion (la variable 'mu', d'après Wikipedia, description).

Aussi, le "lambda" la valeur vous indique la longueur de la liste B, et si vous le souhaitez, vous pouvez déterminer la longueur de la liste A au cours de l'algorithme (lorsque vous rediriger le lien NUL).

Peut-être que je suis au-dessus de la simplification, mais simplement de réitérer la plus petite de la liste et utilisez les derniers nœuds Link que la fusion point?

Alors, où Data->Link->Link == NULL est le point de fin, donnant Data->Link que la fusion point (à la fin de la liste).

EDIT:

Bon, à partir de l'image que vous avez posté, vous analysez les deux listes, le plus petit d'abord. Avec le plus petit de la liste, vous pouvez maintenir les références au nœud suivant. Maintenant, lorsque vous analysez la deuxième liste vous faire une comparaison sur la référence pour trouver d'où la Référence [i] est la référence à LinkedList[i]->Lien. Cela vous donnera le point de fusion. Le temps d'expliquer avec des photos (superposer les valeurs sur l'image de l'OP).

Vous avez une liste chaînée (références indiquées ci-dessous):

A->B->C->D->E

Vous avez une deuxième liste chaînée:

1->2->

Avec la fusion de la liste, les références vont ensuite comme suit:

1->2->D->E->

Par conséquent, vous carte la première "petite" liste (comme la fusion de la liste, qui est ce que nous comptons a une longueur de 4 et de la liste principale 5)

Boucle à travers la première liste, de maintenir une référence de références.

La liste contient les références suivantes Pointers { 1, 2, D, E }.

Nous maintenant à la seconde liste:

-> A - Contains reference in Pointers? No, move on
-> B - Contains reference in Pointers? No, move on
-> C - Contains reference in Pointers? No, move on
-> D - Contains reference in Pointers? Yes, merge point found, break.

Sûr, vous maintenez une nouvelle liste de pointeurs, mais ce n'est pas en dehors de la spécification. Cependant, le premier de la liste est analysé exactement une fois, et la seconde liste ne sera pleinement analysé si il n'y a pas de point de fusion. Autrement, il va se terminer plus tôt (à la fusion point).

cette solution itération de chaque liste qu'une seule fois...pas de modification de la liste nécessaire de trop..si vous pouvez vous plaindre à propos de l'espace..

1) en fait, vous itérer dans la liste 1 et stocker l'adresse de chaque nœud dans un tableau(qui stocke unsigned int valeur)

2) Ensuite vous parcourez la liste 2, et pour chaque nœud de l'adresse ---> de la recherche à travers le tableau que vous trouver un match ou pas...si vous le faites, alors c'est la fusion de nœud

//pseudocode
//for the first list
p1=list1;
unsigned int addr[];//to store addresses
i=0;
while(p1!=null){
  addr[i]=&p1;
  p1=p1->next;
}
int len=sizeof(addr)/sizeof(int);//calculates length of array addr
//for the second list
p2=list2;
while(p2!=null){
  if(search(addr[],len,&p2)==1)//match found
  {
    //this is the merging node
    return (p2);
  }
  p2=p2->next;
}

int search(addr,len,p2){
  i=0;  
  while(i<len){
    if(addr[i]==p2)
      return 1;
    i++;
  }
 return 0;
} 

Espère que c'est une solution valable...

Il n'est pas nécessaire de modifier la liste. Il y a une solution à laquelle nous n'avons qu'à traverser chaque liste une fois.

1. Créer deux piles, permet de dire stck1 et stck2.
2. Traverse 1er de la liste et appuyer sur un exemplaire de chaque nœud de traverse, dans le stck1.
3. Même que l'étape deux, mais cette fois traverser la 2e liste et pousser la copie de nœuds dans stck2.
4. Maintenant, de la pop à partir de deux piles et de vérifier si les deux nœuds sont égaux, si oui, alors le garder en référence. Si non, puis précédente nœuds qui étaient égaux sont en fait de la fusion point que nous recherchions.

Comment à ce sujet:

1. Si vous êtes seulement autorisé à traverser chaque liste qu'une seule fois, vous pouvez créer un nouveau nœud, traverse le premier de la liste pour chaque point de nœud de ce nouveau nœud, et traverse la deuxième liste pour voir si tout nœud est pointant vers votre nouveau nœud (c'est votre point de fusion). Si la deuxième traversée de ne pas conduire à votre nouveau nœud puis les listes initiales n'avez pas de point de fusion.

2. Si vous êtes autorisé à traverser les listes plus d'une fois, vous pouvez traverser chaque liste pour trouver notre leurs longueurs, et si elles sont différentes, omettez le "extra" nœuds au début de la liste la plus longue. Puis il suffit de parcourir les deux listes, une étape à la fois et de trouver la première fusion de nœud.

Nous pouvons résoudre efficacement en introduisant de "isVisited" sur le terrain. Traverse de la première liste et définissez "isVisited" valeur "true" pour tous les nœuds jusqu'à la fin. Maintenant, commencer à partir de la deuxième et de rechercher le premier nœud où le drapeau est vrai ,et Boum, de son point de fusion.

int FindMergeNode(Node *headA, Node *headB)
{
    Node *tempB=new Node;
    tempB=headB;
   while(headA->next!=NULL)
       {
       while(tempB->next!=NULL)
           {
           if(tempB==headA)
               return tempB->data;
           tempB=tempB->next;
       }
       headA=headA->next;
       tempB=headB;
   }
    return headA->data;
}

Un O(n) la complexité de la solution. Mais, sur la base d'une hypothèse.

hypothèse: les deux nœuds sont d'avoir uniquement des entiers positifs.

logique : faire que tous les entiers de la liste 1 à négative. Puis à pied à travers la liste 2, jusqu'à ce que vous obtenez un entier négatif. Une fois trouvé => le prendre, de modifier le signe de retour à la positif et retour.

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {

    SinglyLinkedListNode current = head1; //head1 is give to be not null.

    //mark all head1 nodes as negative
    while(true){
        current.data = -current.data;
        current = current.next;
        if(current==null) break;
    }

    current=head2; //given as not null
    while(true){
        if(current.data<0) return -current.data;
        current = current.next;
    }

}