Ajouter deux grands nombres représentés sous forme de listes chaînées sans inverser les listes chaînées
Supposons que vous avez 2 grands nombres représentés que les listes liées, comment voulez-vous ajouter et de stocker le résultat dans une autre liste liée.
par exemple
a = 2 -> 1 -> 7
b = 3 -> 4
result = 2 -> 5 -> 1
Pouvez-vous ajouter sans renverser les listes liées
source d'informationauteur shreyasva
Vous devez vous connecter pour publier un commentaire.
Pseudocode:
Étape 1. Parcourir les listes chaînées et de pousser les éléments en deux piles distinctes
Étape 2. Pop le top éléments à la fois des piles
Étape 3. Ajouter les éléments (+ de report de précédentes acquisitions), et de stocker le transporter dans une variable temp
Étape 4. Créer un nœud avec la somme et de l'insérer en début de la liste des résultats
Je pense que c'est quelque chose au-delà de contexte, mais peut être très incitatif à la performance de la personne qui a posté cette question.
Voici donc une recommandation:
au lieu de l'utilisation de chaque nœud dans un seul des chiffres du nombre, de l'utilisation de chaque nœud pour stocker un grand nombre(près de la taille d'un entier) et si le plus grand nombre possible vous avez choisi de stocker dans chaque nœud être
x
(votre cas 9) ensuite, vous pouvez afficher votre numéro de représentation dansbase x+1
.où chaque chiffre est un nombre entre 0 et x.
Ce serait vous donner gain de performance significatif que l'algorithme s'exécuter en O(log n) le temps et le besoin du même nombre de nœuds comme contre O(n) dans votre cas , n étant le nombre de chiffres après la virgule de la plus grande des deux addends.
Généralement pour la facilité de votre algorithme, vous pouvez choisir une puissance de 10 de la base, qui s'inscrit dans la portée de votre entier.
Par exemple, si votre numéro de 1234567890987654321 et vous souhaitez le stocker dans la liste, le choix de la base à 10^8 alors votre représentation devrait ressembler à:
87654321-> 4567890 -> 123(little endian)
Voici mon hacky tentative en Java qui s'exécute dans sur O(max(len(a),len(b))). J'ai fourni un exemple complet avec un très simple seule liste liée de mise en œuvre. C'est beaucoup de retard, voici donc le code n'est pas aussi beau que je le souhaiterais - désolé!
Ce code suppose:
Il utilise la récursivité pour propager les sommes et les transporter pour chaque chiffre, et sommes de gauche à droite. Les listes ne sont jamais inversé - les sommes sont effectuées de gauche à droite, et de réaliser se propage jusqu'à la pile récursive. Il pourrait être déroulé dans un processus itératif de solution, mais je ne vous inquiétez pas à ce sujet.
Voici un pseudo-code.
Voici ma tentative, en utilisant les deux listes chaînées et le retour de la somme comme une nouvelle liste en utilisant la récursivité.
1.D'abord traverser les deux listes et trouver les longueurs des deux listes(soit m,n est la longueur).
2.Traverse n-m nœuds de la liste la plus longue et la valeur "prt1' du nœud actuel et "ptr2' au début de l'autre liste.
3.Maintenant appeler la fonction récursive avec l'indicateur à zéro:
4.Maintenant, vous devez ajouter le reste de la n-m nœuds au début de votre liste, vous pouvez le faire directement à l'aide d'une boucle. Veuillez noter que pour le dernier élément dans la boucle, vous devez ajouter le drapeau retourné par la méthode add() de la fonction comme il pourrait y avoir un report.
Si votre question est sans l'aide de la récursivité:
1.Répétez les deux premières étapes, puis de créer votre liste cible initalising tous les éléments avec '0'(assurez-vous que la longueur de la liste est exacte).
2.Traverser les deux listes avec votre liste cible(un pas en arrière).Si vous trouvez de la somme de deux nœuds de plus grand que 10, la valeur dans la liste des cibles comme des '1'.
3.Avec l'étape ci-dessus vous avez pris soin de le réaliser. Maintenant en une seule passe de plus il suffit d'ajouter les deux nœuds modulo 10 et ajouter cette valeur dans le nœud correspondant de la liste des cibles.
sans l'aide de la pile .....
il suffit de stocker le contenu de la liste de liens dans le tableau et effectuer une addition et puis il a de nouveau mis plus en lien liste
code :
Nous pouvons les ajouter à l'aide de la récursivité. Assumer la question est définie comme suit: nous avons des listes
l1
etl2
et nous voulons ajouter en les stockant le résultat dansl1
. Pour des raisons de simplicité supposons que les deux listes ont la même longueur (le code peut être facilement modifié pour fonctionner, pour différentes longueurs). Voici mon travail de Java solution:La plupart des approches ici besoin de plus d'espace pour la Liste a et la Liste b de l'. Ce peut être retiré.
Mon récursive Java mise en œuvre:
Espère que ça aide.
Version finale (pas de liste de reprise, pas de récursivité):
En java, je vais le faire de cette façon
Voici mon premier essai:
résultat est:
3->1->5->5
5->9->2->5->9->9
8->0->8->0->0->0->1
/* spoiler: de la simple récurrence */