Le programme JavaScript ajoute deux nombres représentés par une liste chaînée

Le programme JavaScript ajoute deux nombres représentés par une liste chaînée - Configuration 1

王林

Libérer： 2023-09-08 09:53:07

avant

733 Les gens l'ont consulté

JavaScript 程序添加由链接列表表示的两个数字 - 设置 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.

Entrez

1 -> 2 -> 3 -> null
3 -> 2 -> 4 -> null

Copier après la connexion

Sortie

4 -> 4 -> 7 -> null

Copier après la connexion

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.

Convertir à la méthode numérique

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.

Exemple

// 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);

Copier après la connexion

Sortie

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

Copier après la connexion

Complexité temporelle et spatiale

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.

Une autre façon

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.

Exemple

// 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);

Copier après la connexion

Sortie

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

Copier après la connexion

Conclusion

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!