Maison > Article > interface Web > Le programme JavaScript ajoute deux nombres représentés par une liste chaînée - Configuration 1
Ajouter deux nombres est une tâche simple mais peut s'avérer délicate si les nombres sont donnés sous la forme d'une liste chaînée. Chaque nœud de la liste chaînée contient le numéro du nombre qu'il représente de manière continue du premier nœud au dernier nœud. Nous obtiendrons deux listes chaînées représentant deux nombres différents et nous devrons les additionner et renvoyer le troisième nombre sous la forme d'une liste chaînée.
1 -> 2 -> 3 -> null 3 -> 2 -> 4 -> null
4 -> 4 -> 7 -> null
Explication : Étant donné que le premier nombre est 123, le deuxième nombre est 324 et que leur somme est 447, nous le renvoyons sous forme de liste chaînée.
Dans cette méthode, nous convertissons d'abord le nombre donné de la représentation de liste chaînée en forme entière, puis appliquons une opération d'addition. Après cela, nous convertissons le résultat en une liste chaînée et revenons enfin pour imprimer les données présentes dans la liste chaînée de réponse.
// class to create the structure of the nodes class Node{ constructor(data){ this.value = data; this.next = null; } } // function to print the linked list function print(head){ var temp = head; var ans = "" while(temp.next != null){ ans += temp.value; ans += " -> " temp = temp.next } ans += temp.value ans += " -> null" console.log(ans) } // function to add data in linked list function add(data, head, tail){ return tail.next = new Node(data); } // function to convert linked list to number function LL_to_int(head){ var temp = ""; var cur = head; while(cur != null){ temp += cur.value.toString(); cur = cur.next; } return parseInt(temp); } // function to convert number to linked list function num_to_LL(num){ var str = num.toString(); var head = new Node(str[0]-'0'); var tail = head; for(var i = 1; i<str.length; i++){ tail = add(str[i]-'0',head, tail); } // final number is console.log("The final answer is: ") print(head); } // defining first number var num1 = new Node(1) var tail = num1 tail = add(2,num1, tail) tail = add(3,num1, tail) console.log("The given first number is: ") print(num1) // defining second number var num2 = new Node(3) tail = num2 tail = add(2,num2, tail) tail = add(4,num2, tail) console.log("The given second number is: ") print(num2) // converting both the linked list into the actual values int_num1 = LL_to_int(num1) int_num2 = LL_to_int(num2) var ans = int_num1 + int_num2; // converting number to the linked list num_to_LL(ans);
The given first number is: 1 -> 2 -> 3 -> null The given second number is: 3 -> 2 -> 4 -> null The final answer is: 4 -> 4 -> 7 -> null
La complexité temporelle du code ci-dessus est (M+N), où M et N sont les tailles de la liste chaînée donnée.
La complexité spatiale du code ci-dessus est O(N) car nous créons une nouvelle liste chaînée.
Dans cette méthode, nous ajouterons des éléments de liste chaînée en parcourant de la fin au premier nœud jusqu'à ce que la première valeur de la liste chaînée devienne nulle. Lorsqu'une fois devient zéro, définissez sa valeur sur zéro et déplacez-vous jusqu'à ce qu'ils deviennent tous deux nuls.
// class to create the structure of the nodes class Node{ constructor(data){ this.value = data; this.next = null; } } // function to print the linked list function print(head){ var temp = head; var ans = "" while(temp.next != null){ ans += temp.value; ans += " -> " temp = temp.next } ans += temp.value ans += " -> null" console.log(ans) } // function to add data in linked list function add(data, head, tail){ return tail.next = new Node(data); } // function to convert string to linked list function num_to_LL(str){ var head = new Node(str[str.length-1]-'0'); var tail = head; for(var i = str.length-2; i>=0; i--){ tail = add(str[i]-'0',head, tail); } // final number is console.log("The final answer is: ") print(head); } // function to add values of the linked lists function addLL(ll1, ll2){ var str = ""; var carry = 0; while((ll1 != null) || (ll2 != null)){ if(ll1 == null){ carry += ll2.value; ll2 = ll2.next; } else if(ll2 == null){ carry += ll1.value; ll1 = ll1.next; } else { carry += ll1.value + ll2.value; ll2 = ll2.next; ll1 = ll1.next; } str += (carry%10).toString(); carry /= 10; carry = Math.floor(carry); } if(carry != 0){ str += (carry%10).toString(); } // calling function to print the answer num_to_LL(str); } // defining first number in reverse manner var num1 = new Node(3) var tail = num1 tail = add(2,num1, tail) tail = add(1,num1, tail) console.log("The given first number in reverse manner is: ") print(num1) // defining second number var num2 = new Node(4) tail = num2 tail = add(2,num2, tail) tail = add(3,num2, tail) console.log("The given second number in reverse manner is: ") print(num2) // calling to the add function addLL(num1,num2);
The given first number is: 1 -> 2 -> 3 -> null The given second number is: 3 -> 2 -> 4 -> null The final answer is: 4 -> 4 -> 7 -> null
Dans ce tutoriel, nous avons implémenté du code JavaScript pour ajouter deux nombres donnés sous forme de liste chaînée et renvoyer le résultat sous forme de liste chaînée. Nous avons implémenté deux méthodes avec une complexité temporelle et spatiale O(N).
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!